首页 > 代码库 > 堆排序
堆排序
堆排序
堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。
1.堆
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
2.堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
操作过程如下：
1)初始化堆：将R[1..n]构造为堆；
2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
下面举例说明：
给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。
首先根据该数组元素构建一个完全二叉树，得到
20和16交换后导致16不满足堆的性质，因此需重新调整
这样就得到了初始堆。
此时3位于堆顶不满堆的性质，则需调整继续调整
1 //小堆 2 #include <iostream> 3 using namespace std; 4 5 #define N 1000 6 //6 16 7 3 20 17 8 7 void print(int a[],int len){//打印 8 for(int i = 1; i <= len; i++) 9 cout<<a[i]<<" ";10 cout<<endl;11 }12 void HeadAdjust(int* a,int i,int len){//进行调整，只有一个孩子和有两个孩子两种情况13 int childl = i * 2;14 int childr = i * 2+1;15 if(childr > len && childl <= len){//只有一个孩子16 if(a[i] > a[childl]){17 swap(a[i],a[childl]);18 // cout<<"swap "<<i<<" "<<childl<<endl;19 HeadAdjust(a,childl,len);20 }21 }22 else if(childr <= len){//两个孩子的23 if(a[i] > a[childl] && a[childl] <= a[childr]){24 swap(a[i],a[childl]);25 //cout<<"swap "<<i<<" "<<childl<<endl;26 HeadAdjust(a,childl,len);27 28 }29 else if(a[childr] <= a[childl] && a[i] > a[childr]){30 swap(a[i],a[childr]);31 //cout<<"swap "<<i<<" "<<childr<<endl;32 HeadAdjust(a,childr,len);33 }34 }35 }36 37 void BuildHeap(int a[],int len){38 for(int i = len; i > 0; i--)39 HeadAdjust(a,i,len);40 }41 42 void HeadSort(int* a,int len){43 for(int i = len ; i > 0; i--){44 swap(a[1],a[i]);45 HeadAdjust(a,1,i-1);46 // print(a,len);47 }48 }49 50 int main(){51 52 int n;53 cin>>n;54 int a[N];55 for(int i = 1; i <= n; i++){56 cin>>a[i];57 }58 BuildHeap(a,n);59 // print(a,n);60 HeadSort(a,n);61 print(a,n);62 return 0;63 }
大堆排序实现从小到大
//大堆#include <iostream>using namespace std;#define N 1000//6 16 7 3 20 17 8void print(int a[],int len){//打印 for(int i = 1; i <= len; i++) cout<<a[i]<<" "; cout<<endl;}void HeadAdjust(int* a,int i,int len){//进行调整，只有一个孩子和有两个孩子两种情况 int childl = i * 2; int childr = i * 2+1; if(childr > len && childl <= len){//只有一个孩子 if(a[i] < a[childl]){ swap(a[i],a[childl]); // cout<<"swap "<<i<<" "<<childl<<endl; HeadAdjust(a,childl,len); } } else if(childr <= len){//两个孩子的 if(a[i] < a[childl] && a[childl] >= a[childr]){ swap(a[i],a[childl]); //cout<<"swap "<<i<<" "<<childl<<endl; HeadAdjust(a,childl,len); } else if(a[childr] >= a[childl] && a[i] < a[childr]){ swap(a[i],a[childr]); //cout<<"swap "<<i<<" "<<childr<<endl; HeadAdjust(a,childr,len); } }}void BuildHeap(int a[],int len){ for(int i = len; i > 0; i--) HeadAdjust(a,i,len);}void HeadSort(int* a,int len){ for(int i = len ; i > 0; i--){ swap(a[1],a[i]); HeadAdjust(a,1,i-1); }}int main(){ int n; cin>>n; int a[N]; for(int i = 1; i <= n; i++){ cin>>a[i]; } BuildHeap(a,n); HeadSort(a,n); print(a,n); return 0;}