图解排序算法之堆排序

ゝ一世哀愁。 2022-01-22 09:17 324阅读 0赞

**堆排序**

堆排序是利用**堆**这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

**堆**

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。左边为大根堆，右边为小根堆。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NpbW9uczI0_size_16_color_FFFFFF_t_70][]

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

![1024555-20161217182857323-2092264199.png][]

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

**大根堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]**

**小根堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]**

### **堆排序基本思想及步骤** ###

> **堆排序的基本思想是：将待排序序列构造成一个大根堆，此时，整个序列的最大值就是根顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了** 。

**步骤一 构造初始堆。将给定无序序列构造成一个大根堆（一般升序采用大根堆，降序采用小根堆)。**

a.假设给定无序序列结构如下

![1024555-20161217192038651-934327647.png][]

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

![1024555-20161217192209433-270379236.png][]

4.找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换。

![1024555-20161217192854636-1823585260.png][]

这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。

![1024555-20161217193347886-1142194411.png][]

此时，我们就将一个无需序列构造成了一个大**根**堆。

**步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。**

a.将堆顶元素9和末尾元素4进行交换

![1024555-20161217194207620-1455153342.png][]

b.重新调整结构，使其继续满足堆定义

![1024555-20161218153110495-1280388728.png][]

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

![1024555-20161218152929339-1114983222.png][]

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

![1024555-20161218152348229-935654830.png][]

再简单总结下堆排序的基本思路：

**a.将无需序列构建成一个堆，根据升序降序需求选择大根堆或小根堆;**

**　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;**

**　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。**

### **下面是实现算法的C++代码：** ###

//
    // Created by liushihao on 19-6-5.
    //
    #include "iostream"
    using namespace std;
    
    typedef int KeyType;
    typedef struct
    {
        KeyType key;
        int data;
    }RecType;
    
    void sift(RecType R[], int low, int high) //筛选算法
    {
        int i=low, j=2*i+1;    //R[j]是R[i]的左孩子
        RecType tmp=R[i];
        while(j<=high)
        {
            if(j<high && R[j].key<R[j+1].key)   //找出左右孩子中最大的结点的下标
                j++;
            if(tmp.key<R[j].key)                //如果父节点小于左右孩子中任一结点，则交换
            {
                R[i]=R[j];
                i=j;
                j=2*i+1;                        //使得R[j]是R[i]的左孩子
            } else break;
        }
        R[i]=tmp;
    }
    
    void HeapSort(RecType R[], int n)
    {
        int i;
        for(i=n/2-1; i>=0; i--)   //建立初始堆
        {
            sift(R, i, n-1);    
        }
        for(i=n-1; i>=1; i--)     //每一次循环找一个最大的  然后将最小的放在最末尾 再交换
        {
            swap(R[0], R[i]);
            sift(R, 0, i-1);
        }
    }
    
    int main()
    {
        int n;
        cin>>n;
        RecType R[n];
        for(int i=0;i<n;i++)
        {
            cin>>R[i].key;
        }
        for(int i=0;i<n;i++)
        {
            cout<<R[i].key<<" ";
        }
        HeapSort(R, n);
        cout<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<R[i].key<<" ";
        }
        return 0;
    }

参考文章“[https://www.cnblogs.com/chengxiao/p/6129630.html][https_www.cnblogs.com_chengxiao_p_6129630.html]”

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NpbW9uczI0_size_16_color_FFFFFF_t_70]: /images/20220122/505cd0bb356d4dfa824005ac3c26543f.png
[1024555-20161217182857323-2092264199.png]: /images/20220122/569d446225d5484c9414bccbc0113845.png
[1024555-20161217192038651-934327647.png]: /images/20220122/e80b86d7f375492c87af262cc46740da.png
[1024555-20161217192209433-270379236.png]: /images/20220122/747fb6aaf7c2429a8cb151c5cd147d7e.png
[1024555-20161217192854636-1823585260.png]: /images/20220122/0a4af274ac1243caa0fefad379a574bd.png
[1024555-20161217193347886-1142194411.png]: /images/20220122/62ac57973f4a4fb6a4b63bc1b0bcc578.png
[1024555-20161217194207620-1455153342.png]: /images/20220122/f7240b942b7a4653bf2513fee30a7950.png
[1024555-20161218153110495-1280388728.png]: /images/20220122/97710a0f11bd4fe2a8dab8692ffb5a4b.png
[1024555-20161218152929339-1114983222.png]: /images/20220122/6803dfdeed284ddb97336a37b484e7ca.png
[1024555-20161218152348229-935654830.png]: /images/20220122/825d9285e7e84e82928930911c1ec376.png
[https_www.cnblogs.com_chengxiao_p_6129630.html]: https://www.cnblogs.com/chengxiao/p/6129630.html