排序算法：堆排序

秒速五厘米 2022-04-04 11:00 325阅读 0赞

### 一、前言 ###

堆排序是一种**选择排序**。  
    **选择排序**：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

--------------------

### 二、算法思想 ###

堆排序是利用堆的性质进行的一种选择排序。

动态效果示意图：  
            ![在这里插入图片描述][20181216210840618.gif]

**堆**是一棵**顺序存储**的**完全二叉树**。  
    （1）其中每个结点的关键字都**不大于**其孩子结点的关键字，这样的堆称为**小根堆**。  
    （2）其中每个结点的关键字都**不小于**其孩子结点的关键字，这样的堆称为**大根堆**。

举例来说，对于n个元素的序列\{R0, R1, … , Rn\}当且仅当满足下列关系之一时，称之为堆：  
    （1）Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)  
    （2）Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)  
    其中i=1,2,…,n/2向下取整；  
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NlYWxpcg_size_16_color_FFFFFF_t_70]

如上图所示，序列R\{3, 8, 15, 31, 25\}是一个典型的小根堆。  
    堆中有两个结点，元素3和元素8。  
    元素3在数组中以R\[0\]表示，它的左孩子结点是R\[1\]，右孩子结点是R\[2\]。  
    元素8在数组中以R\[1\]表示，它的左孩子结点是R\[3\]，右孩子结点是R\[4\]，它的父结点是R\[0\]。可以看出，它们**满足以下规律**：  
    设当前元素在数组中以 **R\[i\]** 表示，那么，  
    （1）它的**左孩子结点**是：**R\[2\*i+1\]**;  
    （2）它的**右孩子结点**是：**R\[2\*i+2\]**;  
    （3）它的**父结点**是：**R\[(i-1)/2\]**;  
    （4）R\[i\] <= R\[2\*i+1\] 且 R\[i\] <= R\[2i+2\]。  
    首先，按堆的定义将数组R\[0…n\]调整为堆（这个过程称为创建初始堆），交换R\[0\]和R\[n\]；  
    然后，将R\[0…n-1\]调整为堆，交换R\[0\]和R\[n-1\]；  
    如此反复，直到交换了R\[0\]和R\[1\]为止。

以上思想可归纳为两个操作：  
    （1）根据初始数组去**构造初始堆**（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。  
    （2）每次**交换第一个和最后一个元素，输出最后一个元素**（最大值），然后把剩下元素**重新调整**为大根堆。  
    当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。  
    先通过详细的实例图来看一下，如何构建初始堆。

设有一个无序序列 \{ 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 \}。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NlYWxpcg_size_16_color_FFFFFF_t_70 1]  
    构造了初始堆后，我们来看一下完整的堆排序处理：

还是针对前面提到的无序序列 \{ 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 \} 来加以说明。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NlYWxpcg_size_16_color_FFFFFF_t_70 2]  
    相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。  
    看完上面所述的流程你至少有一个疑问：

**如何确定最后一个非叶子结点？**

其实这是有一个公式的，设二叉树结点总数为 n，则最后一个非叶子结点是第 ⌊n/2⌋ 个。

C++代码：

#include <iostream>
    #include <vector>
    using namespace std;
    
    void HeapAdjust(vector<int> &list, int parent, int length){
        int temp = list[parent];                    // temp保存当前父节点
        int child = 2 * parent + 1;                    // 先获得左孩子
     
        while (child < length){
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (child + 1 < length && list[child] < list[child + 1]){
                child++;
            }
     
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (temp >= list[child]){
                break;
            }
     
            // 把孩子结点的值赋给父结点
            list[parent] = list[child];
     
            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = 2 * parent + 1;
        }
        list[parent] = temp;
    }
    
    vector<int> HeadSort(vector<int> list){
        int length = list.size();
        // 循环建立初始堆
        for (int i = length / 2 - 1; i >= 0; i--){
            HeapAdjust(list, i, length);
        }
     
        // 进行n-1次循环，完成排序
        for (int i = length - 1; i > 0; i--){
            // 最后一个元素和第一元素进行交换
            int temp = list[i];
            list[i] = list[0];
            list[0] = temp;
     
            // 筛选 R[0] 结点，得到i-1个结点的堆
            HeapAdjust(list, 0, i);
            cout << "第" << length - i << "趟排序:";
            for (int i = 0; i < list.size(); i++){
                cout << list[i] << " ";
            }
            cout << endl;
        }
        return list;
    }
    
    void main(){
        int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
        vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
        cout << "排序前:";
        for (int i = 0; i < test.size(); i++){
            cout << test[i] << " ";
        }
        cout << endl;
        vector<int> result;
        result = HeadSort(test);
        cout << "排序后:";
        for (int i = 0; i < result.size(); i++){
            cout << result[i] << " ";
        }
        cout << endl;
        system("pause");
    }

运行结果如下：  
![在这里插入图片描述][20181216212119569.png]

python代码：

# -*- coding:utf-8 -*-
    
    def HeadSort(input_list):
        '''
        函数说明:堆排序（升序）
        Parameters:
            input_list - 待排序列表
        Returns:
            sorted_list - 升序排序好的列表
        '''
    
        def HeadAdjust(input_list, parent, length):
            '''
            函数说明:堆调整，调整为最大堆
            Parameters:
                input_list - 待排序列表
                parent - 堆的父结点
                length - 数组长度
            Returns:
                无
            '''
            temp = input_list[parent]
            child = 2 * parent + 1
    
            while child < length:
                if child + 1 < length and input_list[child] < input_list[child + 1]:
                    child += 1
                if temp >= input_list[child]:
                    break
    
                input_list[parent] = input_list[child]
    
                parent = child
                child = 2 * parent + 1
            input_list[parent] = temp
    
        if len(input_list) == 0:
            return []
        sorted_list = input_list
        length = len(sorted_list)
    
        for i in range(0, length // 2)[::-1]:
            HeadAdjust(sorted_list, i, length)
    
        for j in range(1, length)[::-1]:
            temp = sorted_list[j]
            sorted_list[j] = sorted_list[0]
            sorted_list[0] = temp
    
            HeadAdjust(sorted_list, 0, j)
            print('第%d趟排序:' % (length - j), end='')
            print(sorted_list)
    
        return sorted_list
    
    if __name__ == '__main__':
        input_list = [6, 4, 8, 9, 2, 3, 1]
        print('排序前:', input_list)
        sorted_list = HeadSort(input_list)
        print('排序后:', sorted_list)

运行结果同上。

--------------------

### 三、算法分析 ###

##### 1、堆排序算法的总体情况 #####

![在这里插入图片描述][20181216212411396.png]

##### 2、时间复杂度 #####

首先计算建堆的时间，也就是下面的代码，

// 循环建立初始堆
    for (int i = length / 2; i >= 0; i--){
        HeapAdjust(list, i, length);
    }

n 个结点，从第 0 层至第 logn 层。对于第 i 层的 2i 个点如果需要往下走 logn−i 步，那么把走的所有步相加得：  
    ![在这里插入图片描述][20181216212648478.png]

接下来就是排序的时间，即下面的代码：

// 进行n-1次循环，完成排序
    for (int i = length - 1; i > 0; i--){
        // 最后一个元素和第一元素进行交换
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;
     
        // 筛选 R[0] 结点，得到i-1个结点的堆
        HeapAdjust(list, 0, i);
    }

HeapAdjust() 耗时 logn，共 n 次，故排序时间为 O(nlogn)。  
    堆的存储表示是**顺序的**。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。  
    当想得到一个序列中第**k**个最小的元素之前的部分排序序列，最好采用堆排序。

##### 3、算法稳定性 #####

堆排序是一种**不稳定**的排序方法。  
    因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

--------------------

本文转载自：[https://cuijiahua.com/blog/2018/01/algorithm\_6.html][https_cuijiahua.com_blog_2018_01_algorithm_6.html]

[20181216210840618.gif]: /images/20220404/e7bbb13cee9b49509186271f13886084.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NlYWxpcg_size_16_color_FFFFFF_t_70]: /images/20220404/1922013439bb4d3d8b849b3acff58ee4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NlYWxpcg_size_16_color_FFFFFF_t_70 1]: /images/20220404/d2e772486e654134aade5a02f150976f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NlYWxpcg_size_16_color_FFFFFF_t_70 2]: /images/20220404/6e741517eb8f4c4882c71150dfe02578.png
[20181216212119569.png]: /images/20220404/b5e9ced809ea46408f8b1764ef73ecdd.png
[20181216212411396.png]: /images/20220404/7079aa7344f743aa84dca1ce6a152fd0.png
[20181216212648478.png]: /images/20220404/8004d0a15c9b443e9a44289a90d658c0.png
[https_cuijiahua.com_blog_2018_01_algorithm_6.html]: https://cuijiahua.com/blog/2018/01/algorithm_6.html