以升序为例,堆排序分为两个阶段:
- 构建初始大顶堆(堆中每个节点都比左右child大);
- 对大顶堆,每次都将堆顶元素与最后一个leaf交换,再对剩下的元素构建大顶堆,如此循环n次。
解释
1. 为什么升序/降序构建的是大顶堆/小顶堆?
因为第2步中,每次都是将堆顶元素后置,故数组排序是从后往前完成的,故与升降序表意相反
2. HeapSort第二个参数n是什么?
类似QuickSort,表示数组末尾元素的下标,即arr[n]是没有越界的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
void (int &a, int &b) { int tmp = a; a = b; b = tmp; }
void BuildHeap(int arr[], int start, int end) { int parent = start, lchild = parent * 2 + 1; int maxchild = lchild; while (lchild <= end) { maxchild = lchild; if (lchild + 1 <= end && arr[lchild + 1] > arr[lchild]) { maxchild = lchild + 1; } if (arr[parent] >= arr[maxchild]) { break; } else { swap(arr[parent], arr[maxchild]); parent = maxchild; lchild = 2 * maxchild + 1; } } }
void HeapSort(int arr[], int n) { for (int i = (n - 1)/2; i >= 0; --i) BuildHeap(arr, i, n); for (int i = 0; i < n; ++i) { swap(arr[0], arr[n - i]); BuildHeap(arr, 0, n - i - 1); } }
|
参考
http://blog.csdn.net/u013412497/article/details/52205785
*已修改该参考的代码错误
近期评论