「数据结构」八大排序(超详解 附动图 源码)(6)

动图演示：
注意：实际中并没有删除堆中元素，图中为了方便表示，将交换后的位置画成了空。

代码如下：
// 堆排序void AdjustDown(int* a, int n, int root)//向下调整{ assert(a); int parent = root; int child = parent * 2 1; while (child < n) { if (child 1 < n && a[child 1] > a[child]) { child ; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 1; } else { break; } }}void HeapSort(int* a, int n){ assert(a); //建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //交换 for (int i = n - 1; i > 0; i--) { Swap(&a[i], &a[0]); AdjustDown(a, i, 0); }}
直接选择排序的特性总结：
堆排序使用堆来选数，效率就高了很多。 时间复杂度：O(N*logN) 空间复杂度：O(1) 稳定性：不稳定

5.冒泡排序

冒泡排序应该是我们最熟悉的排序了，在C语言阶段我们就学习了冒泡排序。
他的思想也非常简单：
两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟
一共进行n-1趟这样的交换将可以把所有的元素排好。
(n-1趟是因为只剩两个元素时只需要一趟就可以完成)