C++超详细分析优化排序算法之堆排序

堆排序算法的思路

堆排序算法是一种树形选择排序算法。它的基本思想是：将待排序的序列构造成一个大根堆（或小根堆），此时，整个序列的最大（或最小）值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大（或最小）值），然后将剩余的n-1个序列重新构造成一个堆，这样，每次找出最大（或最小）值的操作就可以比较快速的完成。

堆排序算法的具体步骤

1. 将待排序序列构造成一个大根堆（或小根堆），并保存堆上的元素个数，设为heap_size;

c++
void build_max_heap(int a[], int len, int heap_size) {
for(int i = len / 2 - 1; i >= 0; i--) {
max_heapify(a, i, len, heap_size);
}
}

1. 将堆顶元素与末尾元素进行交换，此时堆顶元素为序列的最大值，调整堆，在堆长度中减去1，将剩余元素再构造成堆，重复此步骤直到堆长度减为1；

c++
void heap_sort(int a[], int len) {
int heap_size = len;
build_max_heap(a, len, heap_size);
for(int i = len - 1; i >= 1; i--) {
swap(a[0], a[i]);
heap_size--;
max_heapify(a, 0, i, heap_size);
}
}

1. 维护堆性质，使得以i为根节点的子树满足堆的定义。

c++
void max_heapify(int a[], int i, int len, int heap_size) {
int l = i * 2 + 1, r = i * 2 + 2, max_idx = i;
if(l < len && a[l] > a[max_idx]) max_idx = l;
if(r < len && a[r] > a[max_idx]) max_idx = r;
if(max_idx != i) {
swap(a[i], a[max_idx]);
--heap_size;
max_heapify(a, max_idx, len, heap_size);
}
}

堆排序算法的优化

1. 尽可能的减少函数调用次数，使用inline关键字修饰重要的函数

```c++
inline void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

inline void max_heapify(int a[], int i, int len, int heap_size) {
int l = i * 2 + 1, r = i * 2 + 2, max_idx = i;
if(l < len && a[l] > a[max_idx]) max_idx = l;
if(r < len && a[r] > a[max_idx]) max_idx = r;
if(max_idx != i) {
swap(a[i], a[max_idx]);
--heap_size;
max_heapify(a, max_idx, len, heap_size);
}
}
```

1. 由于每次构造堆之前已经将最大值剔除，所以构造堆时只需要从剩余元素的一半开始，逐级向上调整即可

c++
void build_max_heap(int a[], int len, int heap_size) {
for(int i = len / 2 - 1; i >= 0; i--) {
max_heapify(a, i, len, heap_size);
}
}

1. 在调整堆性质时，减少交换次数也能有效提升堆排序的效率

c++
void max_heapify(int a[], int i, int len, int heap_size) {
int l = i * 2 + 1, r = i * 2 + 2, max_idx = i;
if(l < len && a[l] > a[max_idx]) max_idx = l;
if(r < len && a[r] > a[max_idx]) max_idx = r;
if(max_idx != i) {
a[i] ^= a[max_idx] ^= a[i] ^= a[max_idx];
--heap_size;
max_heapify(a, max_idx, len, heap_size);
}
}

堆排序算法的时间复杂度及稳定性

堆排序算法的时间复杂度为 O(nlogn)，它是不稳定的排序算法。

堆排序算法的示例说明

示例一

待排序序列：6，8，2，3，5，7，1

构造的大根堆：8，6，7，3，5，2，1

第一次排序后：1，6，7，3，5，2，8

构造的大根堆：7，6，1，3，5，2

第二次排序后：2，6，1，3，5，7

构造的大根堆：6，3，1，2，5

第三次排序后：5，3，1，2，6

构造的大根堆：3，2，1，5

第四次排序后：1，2，3，5

构造的大根堆：2，1，3

第五次排序后：1，2，3

构造的大根堆：2，1

第六次排序后：1，2

示例二

待排序序列：23，51，10，34，12，2，87，63

构造的大根堆：87，63，23，51，12，2，10，34

第一次排序后：34，63，23，51，12，2，10，87

构造的大根堆：63，51，23，34，12，2，10

第二次排序后：10，51，23，34，12，2，63

构造的大根堆：51，34，23，10，12，2

第三次排序后：2，34，23，10，12，51

构造的大根堆：34，12，23，2，10

第四次排序后：10，12，23，2，34

构造的大根堆：23，12，10，2

第五次排序后：2，12，10，23

构造的大根堆：12，2，10

第六次排序后：2，10，12

构造的大根堆：10，2

第七次排序后：2，10

构造的大根堆：10

第八次排序后：10