【博客326】堆排序

内容： 记录常见排序算法里的堆排序

思路：

1、先将数据构建成最小堆或者最大堆（看从小排到大还是从大排到小来决定） 2、每次从堆顶取出一个元素放到数组前面或者后面，然后对剩下的元素进行堆调整 3、依次执行步骤2直至所有元素都已经排序好

应用：

1、可用于对大数据的排序，比如：多路归并中也会用到类似思路 2、堆排序对原始元素的大小顺序不敏感，不会对其排序性能产生太大影响 （不像快排，是有可能退化为冒泡的）

时间复杂度：

建立堆的时间复杂度：O(n) 堆调整的时间复杂度：O(lgn) 整体时间复杂度：O(n) + n * O(lgn) = O(lgn)

代码:

void heap_adjust(int a[], int min, int max) { int tmp = a[min]; for (int i = min * 2; i <= max; i *= 2) { if (i < max && a[i] < a[i + 1]) { i++; } if (a[i] <= tmp) { break; } a[min] = a[i]; min = i; } a[min] = tmp; } void heap_sort(int a[], int len) { for (int i = len / 2; i >= 0; i--) { heap_adjust(a, i, len - 1); } for (int i = len -1; i > 0; i--) { int tmp = a[i]; a[i] = a[0]; a[0] = tmp; heap_adjust(a,0,i - 1); } }