首页 > 代码库 > 堆排序（原理和C语言实现）

堆排序（原理和C语言实现）

2024-07-26 06:54:37   222人阅读

HeapSort 原理：

 （堆排序是不稳定的）

实现堆排序可以看成分为两个部分：

1.从一个无序堆建成一个大顶堆（假设我们要求从小到大排序）

2.在“输出”堆顶元素之后，调整剩余元素成为一个新的堆

建立大顶堆方法：

从最后一个非叶子结点开始向前遍历，每一个遍历到的结点都和它的两个（或者一个）子结点中的最大值比较，如果父结点小于孩子结点的较大值，就交换它们;

这样就可以保证每一个遍历到的结点都是以它为树顶的子树中的最大值，那么遍历完成后堆顶就是整个堆的最大值并且每个子树都是父结点大于孩子结点（相对有序）

调整方法：

将堆顶（整个堆最大的元素）与最后一个叶子结点（并不一定是最小的）交换，这时如果使遍历时用到的数组长度减一，则就“相当于”将最大值取出; 

交换后的堆顶不是剩余堆的最大值，于是从上向下调整，由于这时除了堆顶之外的其他部分都是相对有序的，所以向下交换过程中，只沿着产生交换的路线遍历即可;

 

下面举例说明：（转自：http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html）

     给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。

    首先根据该数组元素构建一个完全二叉树，得到

 
 然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

20和16交换后导致16不满足堆的性质，因此需重新调整

 

这样就得到了初始堆。

 

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

此时3位于堆顶不满堆的性质，则需调整继续调整

 这样整个区间便已经有序了。

 

 

 

 1 void up2down(int *arr, int index, int end)
 2 {
 3     int index_child=(index<<1)+1;
 4     int key=arr[index];
 5     while(index_child<=end){
 6         if(index_child+1<=end&&\
 7 arr[index_child+1]>arr[index_child]){
 8             index_child++;
 9         }
10         if(arr[index_child]<=key){
11             break;
12         }
13         //这里和快排类似，不采用两两交换的算法
14         arr[index]=arr[index_child];
15         index=index_child;
16         index_child=(index_child)>>1+1;
17     }
18     arr[index]=key;
19 }
20 
21 void heap_sort(int *arr, int arr_len)
22 {
23     int index;
24     int temp;
25     //从最后一个非叶子结点向上遍历
26     for(index=(arr_len-1-1)>>1;index>=0;index--){
27         up2down(arr, index, arr_len-1);
28     }
29     for(index=arr_len-1;index>=1;index--){
30         temp=arr[0];
31         arr[0]=arr[index];
32         arr[index]=temp;
33         up2down(arr, 0, index-1)
34     }

35 } 

 

堆排序（原理和C语言实现）


联系
我们