福建省南平市建设局网站,备案查询网站,老年门户网站建设的意义,番禺大石一.堆排序 堆排序即利用堆的思想来进行排序#xff0c;总共分为两个步骤#xff1a; 1. 建堆 升序#xff1a;建大堆 降序#xff1a;建小堆 2. 利用堆删除思想来进行排序 1.1.利用上下调整法实现堆排序
第一步#xff1a;建堆
好了#xff0c;每次建堆都要问自己…一.堆排序 堆排序即利用堆的思想来进行排序总共分为两个步骤 1. 建堆 升序建大堆 降序建小堆 2. 利用堆删除思想来进行排序 1.1.利用上下调整法实现堆排序
第一步建堆
好了每次建堆都要问自己下要建的是什么堆大堆还是小堆呢
我们这里就一一来实现先建大堆
void Print(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}
void Swap(int* p1, int* p2)
{int* tmp *p1;* p1*p2;*p2 tmp;
}
void Adjustup(int* arr2, int child)
{int parent (child - 1) / 2;while (child 0){if (arr2[child]arr2[parent])//注意我们是建的大堆{Swap(arr2[child], arr2[parent]);//传地址才能改变值child parent;parent (child - 1) / 2;}else{break;}}
}
void Heapsort(int* arr, int n)
{//建立堆//问题是你是建大堆还是小堆//我们这里要建大堆for (int i 1; i n; i){Adjustup(arr, i);//利用向上调整法}Print(arr,n);
}
如果你实现过堆的代码相信上面的代码对你来说绝对小菜一碟
由于我们直接调用了打印函数那么我们来看看结果吧。
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void Print(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}
void Swap(int* p1, int* p2)
{int* tmp *p1;* p1*p2;*p2 tmp;
}
void Adjustup(int* arr2, int child)
{int parent (child - 1) / 2;while (child 0){if (arr2[child]arr2[parent])//注意我们是建的大堆{Swap(arr2[child], arr2[parent]);//传地址才能改变值child parent;parent (child - 1) / 2;}else{break;}}
}
void Heapsort(int* arr, int n)
{//建立堆//问题是你是建大堆还是小堆//我们这里要建大堆for (int i 1; i n; i){Adjustup(arr, i);//利用向上调整法}Print(arr,n);
}
int main()
{int arr[] { 4,6,2,1,5,8,2,9 };int sz sizeof(arr) / sizeof(int);Heapsort(arr, sz);return 0;
}
结果 这个是不是就满足了大堆
第二步如何实现排序呢别看上面是从大到小排好的这只是一个巧合我们要学会正确的排序法
如果你对此不清楚那么我要开始表演了。
如果你想我们是大堆这说明最大的数即是堆顶如果我交换数组首尾位置然后这是不是不再是一颗完全二叉树了那么如果我再通过向下调整法来排好重复操作是不是就会得到一个从小到大的数组那么不就排好序了想到这相信你肯定联想到了堆的删除操作下面就让我们利用堆的删除来实现它吧 void Swap(int* p1, int* p2)
{int* tmp *p1;* p1*p2;*p2 tmp;
}
void Adjustdown(int* arr3, int n, int parent)
{int child parent * 2 1;//假设左孩子大//注意我们建的是大堆while (child n){if ((child 1) n (arr3[child] arr3[child 1])){child;}if (arr3[parent] arr3[child]){Swap(arr3[parent], arr3[child]);//交换父子位置parent child;child parent * 2 1;}else{break;}}
}//堆建好了现在实现第二步堆删除
int end n - 1;
while (end 0)
{//堆删除分以下几步//第一步:首尾元素互换Swap(arr[0], arr[end]);//第二步向下调整法调整树根Adjustdown(arr, end, 0);//第三步删除堆尾end--;
}
这对于学过实现堆的你来说依然so easy。
那么就让我们整体检查代码的正确性
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void Print(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}
void Swap(int* p1, int* p2)
{int* tmp *p1;* p1*p2;*p2 tmp;
}
void Adjustup(int* arr2, int child)
{int parent (child - 1) / 2;while (child 0){if (arr2[child]arr2[parent])//注意我们是建的大堆{Swap(arr2[child], arr2[parent]);//传地址才能改变值child parent;parent (child - 1) / 2;}else{break;}}
}
void Adjustdown(int* arr3, int n, int parent)
{int child parent * 2 1;//假设左孩子大//注意我们建的是大堆while (child n){if ((child 1) n (arr3[child] arr3[child 1])){child;}if (arr3[parent] arr3[child]){Swap(arr3[parent], arr3[child]);//交换父子位置parent child;child parent * 2 1;}else{break;}}
}
void Heapsort(int* arr, int n)
{//建立堆//问题是你是建大堆还是小堆//我们这里要建大堆for (int i 1; i n; i){Adjustup(arr, i);//利用向上调整法}Print(arr,n);//堆建好了现在实现第二步堆删除int end n - 1;while (end 0){//堆删除分以下几步//第一步:首尾元素互换Swap(arr[0], arr[end]);//第二步向下调整法调整树根Adjustdown(arr, end, 0);//第三步删除堆尾end--;}Print(arr, n);
}
int main()
{int arr[] { 4,6,2,1,5,8,2,9 };int sz sizeof(arr) / sizeof(int);Heapsort(arr, sz);return 0;
}
结果 如果你是要从大到小排序操作如下
建小堆-》堆的尾删
整体而言有三处改动
1.在void Adjustup(int* arr2, int child)函数中这个语句要改变符号因为是建小堆了。 if (arr2[child]arr2[parent])// 2.在void Adjustdown(int* arr3, int n, int parent)这个函数中这两处符号也要改变原因是因为你现在是小堆向下调整法肯定要调整 if (arr3[child] arr3[child 1])) if (arr3[parent] arr3[child])
整体如下
//表示原来的语句//arr2[child]arr2[parent]
arr2[child]arr2[parent]//if ((child 1) n (arr3[child] arr3[child 1]))
if ((child 1) n (arr3[child] arr3[child 1]))//if (arr3[parent] arr3[child])
if (arr3[parent] arr3[child])
改完之后结果如下 现在我们就要对这个算法进行分析
时间复杂度:建堆为O(NlogN)选数O(N-1logN)
得出结果O(NlogN)(非常牛逼的算法 1.2.只利用向下调整法实现堆排序
大家看上面的代码是不是感觉一个排序要写这么麻烦好不方便啊是的我们其实可以只通过一个向下调整就可以实现堆排序下面看看我的表演吧
步骤还是和上面一样其实就改变了建堆的过程我们现在是通过向下调整法建堆。
看代码
for (int i ; i ; i)
{Adjustdown(arr,,);
}
我们就是要把上面的空缺填好那么该如何写呢
我要告诉你一个概念向下调整建堆是从第一个非叶子节点开始调整我们肯定要调整到0
所以我们可以这样写
for (int i (n - 1 - 1) / 2; i 0; i--)
{Adjustdown(arr,n,i);
}
其他部分不用改变所以整体代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void Print(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}
void Swap(int* p1, int* p2)
{int* tmp *p1;* p1*p2;*p2 tmp;
}
void Adjustdown(int* arr3, int n, int parent)
{int child parent * 2 1;//假设左孩子大//注意我们建的是大堆while (child n){if ((child 1) n (arr3[child] arr3[child 1])){child;}if (arr3[parent] arr3[child]){Swap(arr3[parent], arr3[child]);//交换父子位置parent child;child parent * 2 1;}else{break;}}
}
void Heapsort(int* arr, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){Adjustdown(arr,n,i);}Print(arr, n);//堆建好了现在实现第二步堆删除int end n - 1;while (end 0){//堆删除分以下几步//第一步:首尾元素互换Swap(arr[0], arr[end]);//第二步向下调整法调整树根Adjustdown(arr, end, 0);//第三步删除堆尾end--;}Print(arr, n);
}
int main()
{int arr[] { 4,6,2,1,5,8,2,9 };int sz sizeof(arr) / sizeof(int);Heapsort(arr, sz);return 0;
}
结果
来我们该讨论该算法时间复杂度情况了
建堆O(N)选数O(NlogN)
时间复杂度O(N*logN)
注意该写法不仅简单比上面那种而且效率也比上面的高。
