排序算法：堆排序-蒲公英云

一、前言

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

二、算法思想

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

动态效果示意图：
在这里插入图片描述

堆是一棵顺序存储的完全二叉树。
（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向下取整；
在这里插入图片描述

如上图所示，序列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 }。
在这里插入图片描述
构造了初始堆后，我们来看一下完整的堆排序处理：

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

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

其实这是有一个公式的，设二叉树结点总数为 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");
}

运行结果如下：
在这里插入图片描述

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、堆排序算法的总体情况

在这里插入图片描述

2、时间复杂度

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

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

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

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

// 进行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);
}