C++达成堆排序尝试
发布时间：2021-11-19 14:08:41 所属栏目：教程 来源：互联网
导读：对排序的实现思路有两种 第一种：1.构建最小堆。2.将最小堆的堆顶元素取出放到辅助数组的0号下标。3.重新调整成最小堆（向上调整） 4.重复2-3 第二种：1.构建最大堆。2.将堆顶元素（0号）与最后一个元素调换位置。3.最后一个元素不变，剩下的数据调整成最大
|
对排序的实现思路有两种 第一种：1.构建最小堆。2.将最小堆的堆顶元素取出放到辅助数组的0号下标。3.重新调整成最小堆（向上调整） 4.重复2-3 第二种：1.构建最大堆。2.将堆顶元素（0号）与最后一个元素调换位置。3.最后一个元素不变，剩下的数据调整成最大堆。 4.重复2-3。 这里用的是第二种方式。 几点说明： 1.构建堆用的是数组来存储，即堆顶为s[0],第一层为s[1],s[2]以此类推。 2.下面的程序可能存在bug，因为是笔者用一组写在代码里面的数组来测试的。旨在说明问题。 3.为了方便，所有函数的参数都传进数组，直接在数组上做位置调整（对于数组来说，似乎也只能这么做）。 4.堆排序应该是 heap sort 英语没学好真是悲哀。 直接上代码： //Sort.h 不好意思写成了头文件 #include<iostream> using namespace std; int Max(int s[],int a,int b)//取两数中较大的数的下标 { return s[a]>s[b]?a:b; } /* int Min(int s[],int a,int b) { return s[a]<s[b]?a:b; } */ void swap(int s[],int a,int b)//交换两个数的位置 { int temp; temp = s[a]; s[a]=s[b]; s[b] = temp; } void FixDown(int s[],int a,int n)//向下调整算法 { int temp = a;//这句没什么用，既然写在这里了就不删掉了。 int max = Max(s,temp*2+1,temp*2+2);//取最大值，在下面用到 if(s[temp]>=s[max]||(temp*2+2)>n||(temp*2+1)>n)//如果已经是局部（以s[temp]为根的）最大堆，或者s[temp]是叶子节点，直接返回 return; if(s[temp]<s[max])//否则如果不是局部最大堆，调整。 { swap(s,temp,max);//交换s[temp]和其叶子节点中较大的那个的数据。（如果不是最大那个的话调整完了还不是最大堆，而程序不会察觉） FixDown(s,max,n);//递归 } } void Head(int s[],int n)//构造最大堆，只在一开始的时候用，其实也是调用向下调整算法 { for(int i=(n-1)/2;i>=0;i--)//注意这里循环。向下调是从倒数第二层不断网上调整的。 { FixDown(s,i,n-1); } } void HeadSort(int s[],int n)//排序 { Head(s,n);//=====注意：创建最大堆（把数组里面的元素重排） int j=n-1;//数组尾部 while(j>0) { if(s[0]>s[j])//这句主要是最后一次的时候用。没有if也没关系 { swap(s,0,j);//调换 FixDown(s,0,j-1);//向下调整。注意此时调整的最后一个元素是temp[j-1],不会访问到j，也就是说j被固定了。 } j--; } } void Sort(int s[],int low,int high)//sort函数，外部接口，可以忽视。因为里面其实就是一条语句，调用上面的函数 { HeadSort(s,high); } void Show(int s[],int n) { for(int i=0;i<n;i++) cout << s[i] << " "; } 下面是测试文件 #include"Sort.h" int main() { //int s[]={1,23,3,45,23,5,6,741,2,8,561,395,123,5110}; int s[] = {1,2,3,4,5,6,7,8,9,10}; int n = 10; Sort(s,0,n); cout << "排序后："; Show(s,n); return 0; } 程序的运行过程是这样子的： 1.数组传进来，调用Sort函数。之所以写成这么函数，是因为以后写别的排序算法的时候，在里面调用就可以了，练练自己程序扩展的用法。 2.调用堆排序函数--》Headsort函数 《----算法从这里开始 3.先把数组调整成最大堆==》Head函数 4.现在拿到最大堆之后，s[0]跟s[j]换（j=n-1）。重新调整，循环。 完成。 补充：关于向下调整，如果上面讲的不清楚，可以找相应的博客来看，那种带图片分析的，一看就懂。  （编辑：东莞站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
