算法-堆排序

赶紧让你的大脑来一套广播体操

前言

慢慢的，我们脱离了”小学生“算法，开始接触一些需要绕圈子的思路，赶紧沉浸入堆排序的头脑风暴当中吧。

简介

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

核心思想

1. 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素。
2. 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
4. 直到无序区只有一个元素为止。

示例

建立最大堆

1. 这里有一个数组{100,5,3,11,33,6,8,7}，首先我们将数组我们将数组从上至下按顺序排列，转换成二叉树：一个无序堆。
   

   堆排序-原始数组.png

2. 每一个三角关系都是一个堆，上面是父节点，下面两个分叉是子节点，两个子节点俗称左孩子、右孩子；如果一个孩子都没有的，不形成堆，只能做别人的孩子(啧啧啧)

   
   堆排序-无序堆.png

3. 转换成无序对之后，我们要努力让这个无序堆变成最大堆或是最小堆，本文是建最大堆—即每个堆里，都实现父节点的值都大于任何一个子节点的值。要实现最大堆并不简单。

   
   堆排序-4个堆.png

4. 从最后一个堆开始，即左下角那个没有右孩子的那个堆开始；首先对比左右孩子，由于这货没有右孩子(真是惨)，所以只能用左孩子了，左孩子的值比父节点的值小所以不需要交换。如果发生交换，要检测子节点是否为其他堆的父节点，如果是，递归进行同样的操作。

5. 第二次对比红色三角形内的堆，取较大的子节点，右孩子8胜出，和父节点比较，右孩子8大于父节点3，升级做爸爸，与3交换位置，3的位置没有子节点，这个堆建成最大堆。

   
   堆排序-第二次排序.png

6. 对黄色三角形内堆进行排序，过程和上面一样，最终是右孩子33占领爸爸宝座，被交换的右孩子下面也没有子节点，所以直接结束对比。

   
   堆排序-第三次排序.png

7. 最顶部绿色的堆，堆顶100比左右孩子都大，所以不用交换，至此最大堆建成。

扩大有序区

1. 下面进入第二阶段，扩大有序区，首先将堆顶100交换至最底部7的位置，7升至堆顶(终于做爸爸了)，100所在的底部位置即为有序区，有序区不参与之后的任何对比。

   
   堆排序-有序区1.png

2. 在7升至顶部之后，对顶部重新做最大堆调整，左孩子33代替7的位置。

   
   堆排序-第四次排序.png

3. 在7被交换下来后，下面还有子节点，所以需要继续与子节点对比，左孩子11比7大，所以11与7交换位置，交换位置后7下面为有序区，不参与对比，所以本轮结束，无序区再次形成一个最大堆。

   
   堆排序-第五次排序.png

4. 将最大堆堆顶33交换至堆末尾，扩大有序区；

   
   堆排序-第六次排序.png

5. 不断建立最大堆，并且扩大有序区，最终全部有序。

   
   堆排序-全部有序.png

C语言代码

#pragma mark - 堆排序
void printfHeap (int arr[], int len) {
    int line = 0;
    for (int i = 0; i<len; i++) {
        printf("%d\t",arr[i]);
        if (i==line) {
            printf("\n");
            line = line==0?2:line+line*2;
        }
    }
    printf("\n");
}

void adjustHeap (int arr[], int len, int parentIndex) {
    
    int targetChildIndex = -1;
    
    // 左右孩子的索引
    int leftChildIndex  = parentIndex*2+1;
    int rightChildIndex = parentIndex*2+2;
    
//    printf("未完成调整堆 %d\n",parentIndex);
//    printfHeap(arr,len);
    
    // 找出最大的孩子 先左后右
    if (leftChildIndex > len-1) {
        // 没有左右孩子 退出循环
        return;
    }else if (rightChildIndex > len-1) {
        // 只有左孩子 直接用左孩子
        targetChildIndex = leftChildIndex;
    }else{
        // 左右孩子都有 取出大的那个孩子
        targetChildIndex = arr[leftChildIndex]>arr[rightChildIndex]?leftChildIndex:rightChildIndex;
    }
    
    // 如果孩子大于父节点 则互相交换
    if (arr[targetChildIndex] > arr[parentIndex]) {
        int temp = arr[targetChildIndex];
        arr[targetChildIndex] = arr[parentIndex];
        arr[parentIndex] = temp;
        
//        printf("完成调整堆\n");
//        printfHeap(arr,len);
        adjustHeap(arr, len, targetChildIndex);
    }
}

void heapSort (int arr[], int len) {
    if (len < 2) {
        return;
    }
    printf("原始数据\n");
    printfArr(arr, len);

    // 初始化最大堆
    for (int i = (len-1)/2; i >= 0; i--) {
        adjustHeap(arr, len, i);
    }
    printf("初始化完成\n");
    printfHeap(arr,len);
    

    for (int i = len - 1; i > 0; --i) {
        if (arr[0] > arr[i]) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
        }
        printf("交换后\n");
        printfHeap(arr, len);

        adjustHeap(arr, i - 1, 0);
        printf("调整后\n");
        printfHeap(arr, len);
    }
    printf("最终堆\n");
    printfHeap(arr,len);
    
    printfArr(arr, len);
}

时间复杂度

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的，平均时间复杂度为：O(N*logN)。

总结

是不是看着就觉得复杂呢，个人觉得有时候直接看代码加画图能更快地了解算法的思路。