排序算法进阶-堆排序

青旅半醒 2022-05-31 09:07 171阅读 0赞

### 堆排序是一种高效的排序方法，在某种意义上说排序速度要优于快速排序； ###

#### 堆排序不需要递归进行，不需要辅助空间；时间复杂度稳定为 n \* log2 ^ n; ####

//定义一个数组
    int num[] = {
       3,2,4,5,7};

**下面是堆排序时的抽象空间图:**  
![堆排序][SouthEast]  
***每一个父节点,都对应一个子节点,***   
左子叶为 a \* 2 + 1 ; 右子叶为 a \* 2 + 2;  
***而最后一个有子叶的父节点为 len / 2 - 1; 这里为 1;***

**进行堆排序第一步是要构造一个大定堆,或者是小顶堆 使其满足堆定义;**  
*从最后一个非子叶的父节点开始*  
![堆排序][SouthEast 1]

![堆排序][SouthEast 2]  
这里发现下面的 值为 3 的节点乱序了:  
![堆排序][SouthEast 3]  
***这时构造完了一个大顶堆 - 既父节点比任意一个子节点都要大;***  
接下来就是 交换元素并且保持大堆顶 重复步骤:  
![堆排序][SouthEast 4]  
这时发现大堆顶不成立了, 使其满足大堆顶  
![堆排序][SouthEast 5]  
接下来继续交换 和最后一个元素 同时使其满足堆定义:  
![堆排序][SouthEast 6]  
![堆排序][SouthEast 7]  
最后排序结束:  
![堆排序][SouthEast 8]

#### 堆排序可以解析为两个步骤: ####

##### 1. 构造堆顶 #####

##### 2. 交换元素, 并维持堆顶 #####

发现这两个步骤中有相同的成分 就是 构造堆顶的代码:  
那么最后的代码如下:

#include <cstdio>
    void f(int a[], int i, int len)
    {
        int temp;
        int k;
        temp = a[i];//记录当前节点的值
        //左节点 
        for( k = i * 2 + 1; k < len; k = k * 2 + 1 )
        {
            //如果左节点小于右节点 确定与左节点交换还是右节点
            if( k + 1 < len && a[k] < a[k+1] )
            {
                k++;//下标边成右节点 与 右节点交换 就推到右节点
            }
            if( temp < a[k] )
            {
                //把 左右叶最大值 赋给此节点
                a[i] = a[k];
                i = k;
            }else //如果 叶子的数 都 与父叶子 构成 堆定义就跳出
                break;
        }
        //将此节点元素 放到 该放的地方
        a[i] = temp; 
    // 将左右叶 最大给当前父节点 将父节点的值 向后放 形成堆定义
    }
    int main()
    {
        int a[] = {3,2,4,5,7};
        int len = sizeof(a) / sizeof(a[0]);
        int i;
        int temp;
        // i为最后一个父节点
        for(i = len / 2 - 1; i >= 0; i--)
        {
            f(a, i, len);
        }
        //i为最后 一个元素 同时 也记录未排序的长度
        for( i = len - 1 ; i > 0; i--)
        {
            temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            f(a, 0, i);
        }   
    }

**当然还可以不把共同部分包装成函数 这样更好理解记忆:**  
代码如下:

#include <cstdio>
    int main()
    {
        int i;
        int j;
        int a[] = {
       3,2,4,5,7};
        int temp;
        int len = sizeof(a) / sizeof(a[0]);
        // 构造大堆顶
        for( i = len / 2 - 1; i >= 0; i --)
        {
            int m = i;
            temp = a[i];
            for(j = m * 2 + 1; j < len; j = j * 2 + 1)
            {
                if( j + 1 < len && a[j + 1] > a[j])
                    j++;
                if( temp < a[j])
                {
                    a[m] = a[j];
                    m = j;
                }else 
                    break;
            }
            a[m] = temp;
        }
        // 交换第一个元素和 最后一个未交换过的元素
        for(i = len - 1; i > 0; i --)
        {
            temp = a[0];
            a[0] = a[i];
            a[i] = temp;
    
            // 维持大堆顶
            int m = 0;
            temp = a[0];
            for(j = m * 2 + 1; j < i; j = j * 2 + 1)
            {
                if( j + 1 < i && a[j + 1] > a[j])
                    j++;
                if( temp < a[j])
                {
                    a[m] = a[j];
                    m = j; 
                }else 
                    break;
            }
            a[m] = temp;
        }
    }

[SouthEast]: /images/20220531/05b116955c804171a6b25727e9898814.png
[SouthEast 1]: /images/20220531/e5c382dd38654df4a54e9dd40c7c7410.png
[SouthEast 2]: /images/20220531/da0d83bbf9204a5b8669a59450070766.png
[SouthEast 3]: /images/20220531/7692c4ada5f247869c3401fea7533de4.png
[SouthEast 4]: /images/20220531/b31197d6c14341cb8803078230ca4bf0.png
[SouthEast 5]: /images/20220531/0c533ea1671a4ae1b8f351e1a8bcc1ba.png
[SouthEast 6]: /images/20220531/48a5fbb2ddda4297a702d56684501620.png
[SouthEast 7]: /images/20220531/81eea14c49b24830a1c0887b3cfa8797.png
[SouthEast 8]: /images/20220531/890ea214594e4d84b475cbf1b91ac12f.png