堆排序【算法与数据结构-3】
2013-09-18
堆积排序(Heap Sort
)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
- 时间复杂度:
O(NlgN)
- 空间复杂度:
O(1)
- 不稳定
C 语言代码:
#include <stdio.h>
void swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
// 调整以index=i的元素为根的子树,使这个子树成为最大堆。
// O(lgN)
void maxHeapify(int* a, int i, int N) {
int left = 2 * i + 1; // index从0计数,Left则为 2*i+1,Right则为2*i+2
int right = 2 * i + 2;
int largest = i; // 初始化
if (left < N && a[left] > a[i]) {
largest = left;
}
else {
largest = i;
}
if (right < N && a[right] > a[largest]) {
largest = right;
}
if (largest != i) {
swap(&a[i], &a[largest]);
maxHeapify(a, largest, N);
}
}
// 建立最大堆
// 这个过程相当于递归地去调整每一个子树。而叶子节点可以看做只是一个节点的堆,可以不用调整,所以只用调整非叶子节点,当index从0开始的时候,非叶子节点的最大序号是 (N-1)/2。
// Heap is a[0]~a[N-1].
void buildMaxHeap(int* a, int N) {
int i = (N-1)/2;
for (i = (N-1)/2; i >= 0; i--) {
maxHeapify(a, i, N);
}
}
// 堆排序
void heapSort(int* a, int N) {
buildMaxHeap(a, N); // 整个数组建立为堆结构
int i = N-1;
for(i = N-1; i >= 1; i--) {
// 把堆顶元素(即堆中最大的元素)和数组最后的元素互换,然后把这个前堆顶元素从堆中“去掉”,再调整一下新的堆。如此循环往复,就把较大的元素依次从数组尾部到头部排序下来了。
swap(&a[0], &a[i]);
maxHeapify(a,0,i);
}
}
int main() {
int a[10] = {1, 2, 10, 9, 7, 8, 6, 5, 3, 4};
heapSort(a, 10);
int i = 0;
for (i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}