个人对堆排序的理解
- 第一步：是创建length堆，根节点要比子结点大。
- 第二步：把最父结点与最后一个叶子节点交换。这样堆被破坏。
- 第三步：创建 length-1 的堆。跳转到第一步，一直循环到，length=0 停止。
- 堆排序快就快在，在创建的堆里找最大值相当于折半查找的速度非常乐观。不用不全部扫一遍。
时间复杂度
- 平均速度 o(n*logn)
- 不稳定排序
C版本
#include <stdio.h>
/*
s: 待比较 的节点
分三步走
1.比较s节点下左右子节点的哪一个大
2.其中大的一个节点 与 s节点 比较大小。
3.如果 子节点没有s大 则结束， 比s节点大就交换他们的数值，然后继续向子节点
*/
void HeapAdjust(int H[],int s, int length)
{
int temp = H[s];
int child = 2 * s + 1; //这里child是左孩子的位置，child+1代表右孩子
while (child < length) { //防止 越界。
if (child+1 < length && H[child]<H[child+1]){//防止越界 且，找到左右孩子哪一个比较大。
child++;//右孩子大
}
if (H[child] > H[s]){//比父节点的数值大
H[s] = H[child];//复制给 s 节点
s = child; //调整 s，下一个节点
child = 2 * s + 1;
H[s] = temp;// 交换
}else{
break; //子节点没有比父节点大
}
}
}
///初始化 堆
void BuildingHeap(int H[], int length)
{
///i 等于 最后一个有孩子的结点位置， 一直从堆底走到堆顶。
for(int i = (length - 1) / 2; i >= 0; i--)
HeapAdjust(H,i,length);
}
///堆排序
void HeapSprt(int H[],int length)
{
BuildingHeap(H, length);//创建初始化堆
///这里是 从堆里选择最大的跟节点与跟最后节点交换，后堆排序
//然后堆次大的与倒数第二的节点交换，后堆排序
// 节点与根节点重合结束，从小到大排序结束
for (int i = length - 1; i > 0; i--)
{
int temp = H[0]; H[0] = H[i]; H[i] = temp; ///把 栈顶交换了。
HeapAdjust(H, 0, i);
}
}
int main(){
int a[10] = {8,9,7,0,3,4,5,2,1,6};
HeapSprt(a, 10);
for (int j = 0; j<10; j++) {
printf("%d ",a[j]);
}
printf("\n");
}
-
看我那么可爱n(≧▽≦)n
- 关注我的微薄 (梁同桌)：http://weibo.com/tongrenyinsheng
- 个人博客： http://www.liangtongzhuo.com
- ios 个人写的app （同人音声）ASMR音乐
