我所理解的堆排序算法 堆排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。 堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。 二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。 堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。template <class T>void Insert(T a[], int len, T x)//把x插入到原长度为len的二叉堆，注意保证新二叉堆不越界{ int i; for (i=len; i/2>0 && a[i/2]>x; i/=2) a[i] = a[i/2]; a[i] = x;} template <class T>T DeleteMin(T a[], int len)//删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆{ if (len == 0) exit(1); T min = a[1];//二叉堆的根 T last = a[len--];//二叉堆的最后一个元素 int c; int i; for (i=1; i*2<=len; i=c)//把二叉堆的某些元素往前移，使得新得到的序列仍为二叉堆 { c = i * 2;//i的左儿子 if (c != len && a[c+1] < a[c])//若i有右儿子，且右儿子小于左儿子，c指向右儿子 c++; if (last > a[c])//若i的小儿子小于二叉堆的最后一个元素，把其移到i的位置 a[i] = a[c]; else break; } a[i] = last; //把二叉堆的最后一个元素放到适当的空位，此时得到的序列仍为二叉堆 return min;} template <class T>void HeapSort(T a[], int len){ T *ca = new T[len+1]; //复制原数组到二叉堆 ca[0] = 0; for (int i=0; i<len; i++) //把元素依次插入到二叉堆 Insert(ca, i+1, a[i]); for (int i=0; i<len; i++)//依次提取二叉堆的根作为排序后的数组的元素 { a[i] = DeleteMin(ca, len-i); } a[len-1] = ca[1]; //注意不能忘了最后一个元素 delete []ca;} 在《数据结构习题与解析》（李春葆 编著 清华大学出版社）中看到一个类似的算法，它是把原数组构建成一个大顶堆，然后把大顶堆的第一个元素与最后一个元素交换；再把前n-1个元素重新构造成一个大顶堆，把新大顶堆的第一个元素与最后一个元素交换；依此类推，直到新大顶堆只有一个元素，这样就得到了一个有序的二叉堆。算法如下：template <class T>void HeapSort(T a[], int len){ T *ca = new T[len+1]; ca[0] = 0; for (int i=0; i<len; i++) ca[i+1] = a[i]; for (int i=len/2; i>0; i--) //建立初始堆 HeapAdjust(ca, len, i); for (int i=len; i>1; i--)//进行len-1次循环，完成堆排序 { Swap(ca[1], ca[i]); //新大顶堆的第一个元素与最后一个元素交换 HeapAdjust(ca, i-1, 1);//筛a[1]元素，得到i-1个元素的堆 } for (int i=0; i<len; i++) a[i] = ca[i+1]; delete []ca;} template <class T>void HeapAdjust(T a[], int len, int left) //将i与其小儿子交换位置{ if (len == 0) exit(1); T x = a[left]; int i = left; int c = 2 * i; while (c <= len) { if (c < len && a[c+1] > a[c])//若i有右儿子，且右儿子大于左儿子，c指向右儿子 c++; if (last < a[c])//若i的大儿子大于二叉堆的最后一个元素，把其移到i的位置 { a[i] = a[c]; i = c; c = 2 * i; } else break; } a[i] = x; //把原二叉堆的第一个元素放到适当的空位} template <class T>void Swap(T & a, T & b){ T t = a; a = b; b = t;} 还有一种方法是每次都要重新调整大顶堆，使得父亲比儿子大，这样调整的函数较简单，但因为每次都要遍历一半的元素，时间复杂度较大。算法如下：template <class T>void HeapSort(T a[], int len){ T *ca = new T[len+1]; ca[0] = 0; for (int i=0; i<len; i++) ca[i+1] = a[i]; for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆 HeapAdjust(ca, len, i); Swap(ca[1], ca[len]); //把大顶堆的第一个元素与最后一个元素交换 for (int i=len-1; i>0; i--) { for (int j=i/2; j>0; j--)//遍历长度为i的堆，得到新的大顶堆 HeapAdjust(ca, i, j); Swap(ca[1], ca[i]); } for (int i=0; i<len; i++) a[i] = ca[i+1]; delete []ca;} template <class T>void HeapAdjust(T a[], int len, int i) //将i与其小儿子交换位置{ int c = 2 * i; if (c < len) { T & max = (a[c] > a[c+1])? a[c] : a[c+1]; if (a[i] < max) Swap(a[i], max); } else { if (a[i] < a[c]) Swap(a[i], a[c]); }} template <class T>void Swap(T & a, T & b){ T t = a; a = b; b = t;} 模仿构造大顶堆的方法，我们可以调用HeapAdjust()构造一个二叉堆，并提取二叉堆的根到新数组，然后把原二叉堆的最后一个元素放到根的位置，再调用HeapAdjust()构造一个新二叉堆，依此类推。算法如下：template <class T>void HeapSort(T a[], int len){ T *ca = new T[len+1]; ca[0] = 0; for (int i=0; i<len; i++) ca[i+1] = a[i]; for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆 HeapAdjust(ca, len, i); a[0] = ca[1]; ca[1] = ca[len]; //把二叉堆的最后一个元素放到根的位置 for (int i=len-1; i>0; i--) { for (int j=i/2; j>0; j--) HeapAdjust(ca, i, j); a[len-i] = ca[1]; ca[1] = ca[i]; //把二叉堆的最后一个元素放到根的位置 } delete []ca;} template <class T>void HeapAdjust(T a[], int len, int i){ int c = 2 * i; if (c < len) { T & min = (a[c] < a[c+1])? a[c] : a[c+1]; if (a[i] > min) Swap(a[i], min); } else { if (a[i] > a[c]) Swap(a[i], a[c]); }} template <class T>void Swap(T & a, T & b){ T t = a; a = b; b = t;} 后面两种方法采用的是递归，容易理解，但时间复杂度较高，因为比前两种要慢上很多，所以不可能是O（nlogn），估计是O（n^2），但具体我也不会算，请高手指教。
评论