排序算法—堆排序

堆排序

以前我们的都是在顺序存储的线性链表上应用分治法的算法,比如双端同时开始查找(快排，归并等等).来提高算法的效率. 现在我们来了解不同寻常的排序方法.对存储在顺序表中的二叉树进行堆排序,从而得出我们期望的有序序列. 有没有感觉起跑线都不一样.以往都是优化算法,谁能想到优化结构呢？

知识点.

用数组来实现树相关的数据结构也许看起来有点古怪，但是它在时间和空间上都是很高效的。并不是每一个最小堆都是一个有序数组！要将堆转换成有序数组，需要使用堆排序。堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。 例如，在一个最大堆中，最大的那一个元素总是位于index 0的位置，但是最小的元素则未必是最后一个元素。 唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

步骤分析

堆排序的基本思想是：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。（相当于将极值下沉到数组末尾）然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

升序采用大顶堆，降序采用小顶堆

问题来了,如何把一个无序序列构建成堆呢？

堆结构 {10,5,9,1,2,7,8} 10 5 9 1 2 7 8 in memory unit : index 0 1 2 3 4 5 6 node_v 10 5 9 1 2 7 8 tree_level 1 2 2 3 3 3 3 // 以根结点为第一层 根的孩子为第二层

首先,我们观察上图堆结构中结点的大小关系:

在堆中，在当前层级所有的节点都已经填满之前不允许开是下一层的填充：顺序表中父节点总是在子节点的前面父结点与子结点在顺序表中的索引存在着映射关系:K(i) : left_child_index : K(2i + 1) | right_child_index K(2i+2)在大顶堆中,level(i)层上的结点必定会大于level(i+1)上的结点.但是同一层上属于同一双亲结点的两个子结点谁大谁小是自由的.

所以,用序列下标之间的数学公式来描述以下大顶堆``小顶堆

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 我们首先需要将无序序列假设为一个无序堆,然后找到无序堆中最低层的开始结点(为什么要从次底层开始？因为这样就不用分别处理终端结点和非终端结点了)找到最底层后与上一层的结点进行比较,这将是一个自叶子结点至堆顶的筛选过程(路径上的结点两两比较,大者上升).循环筛选从而构建我们期望的大顶堆.

那么如何找到无序堆中最低层呢?根据二叉树的数学特性: 如果将原始序列看作一棵完全二叉树,则最后一个非终端结点必定为第|n/2|个元素..所以筛选需要从第[n/2]个元素开始.

void external_sort(int a[],int len) { int index; int array_len = len; // array_len/2 - 1 是当前无序堆中第一个非终端结点在数组中的下标 for( index = array_len/2 - 1; level >= 0 ; level-- ){ // i : 当前层中结点存储在顺序表中的 开始索引 // array_len - 1 : 当前层中结点存储在顺序表中的 结束索引 heap_sort(a,i,array_len - 1); } }

代入{10,5,9,1,2,7,8}序列进行分析

实例

#include <stdio.h> #define MAX_SIZE 10 int wait_sort[MAX_SIZE] = {11,15,20,13,17,65,27,49,99,18}; //#define MAX_SIZE 3 //int wait_sort[MAX_SIZE] = {15,11,20}; void show(int * s,int length) { int i ; for(i=0;i<length;i++){ printf(" %d ",s[i]); } printf("\n"); } void swap(int * i,int * j) { int temp; temp = *i; *i = *j; *j = temp; } void build_max_heap(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) //若子节点指标在范围内才做比较 { if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; //如果父节点大於子节点代表调整完毕，直接跳出函数 if (arr[dad] > arr[son]) { break; //否则交换父子内容再继续子节点和孙节点比较 } else { swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; } } } // adjust 调整 // 保障从终端 到 当前 结点的路径是有序的,然后层次逐渐上升.没有多余的比较 void build_min_heap_sort(int a[],int pos,int len) { int temp = a[pos]; int child; // pos = child 代表向下（向着叶子结点方向 进行 两两比较） // 最终为 temp 选取一个合适的位置. for(; 2 * pos + 1 <= len ; pos = child ) { // 首先计算出当前结点的左子结点在顺序表中的索引值 child = 2 * pos + 1; // 选出 左右子结点 中较小的一个 if(child < len && a[child] > a[child + 1]){ child++; } // 选出 父 子 中值较小的结点，上升 ，因为要构建出小顶堆 if(a[child] < temp){ a[pos] = a[child]; } else { break; } } // 归位 a[pos] = temp; } void heap_sort(int a[],int len) { int i; // 先构建一个小顶堆 for(i = len/2 - 1;i>=0;i--){ build_max_heap(a,i,len-1); } show(wait_sort,MAX_SIZE); for(i = len - 1;i>=0;i--){ // 构建完成小顶堆后 ,将根结点下沉到数组的末尾,依次得出 最小值，次小值... swap(&a[0],&a[i]); build_max_heap(a,0,i-1); } } int main(void) { heap_sort(wait_sort,MAX_SIZE); show(wait_sort,MAX_SIZE); return 0; }

复杂度分析

与快速排序相比,堆排序在最坏情况下,其时间复杂度也为O(nlogn),这是堆排序的优点.同时它的辅助存储为O(1).非稳定排序. 对于记录较少的文件不推荐使用堆排序.

参考资料

https://www.jianshu.com/p/6b526aa481b1