转载

堆排序（c++第一次尝试）

对排序的实现思路有两种

第一种：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; }