堆排序算法实现思想个人理解

1.概述：堆排序是简单选择排序的改进算法，简单选择排序在待排序的个数据中选择一个最小的元素需要进行n-1次的比较，但是并没有将每一次循环的结果保存下来，在下一次循环中，有很多比较已经在上一次的循环中做过了，但由于上一次循环时没有保存这些比较结果，所以下一次循环时又要重复这些比较操作，因此数据的比较次数较多。堆排序可以做到每次在选择最小记录的同时，根据比较结果对其他元素做出相应的调整。
2.大顶堆与小顶堆
- 从上面的两幅图可以看出，它们都是完全二叉树。下面给出堆的定义：
  - 大顶堆：每个结点的值都大于或等于其左右孩子结点的值，根结点的值一定是所有结点中最大的
  - 小顶堆：每个结点的值都小于或等于其左右孩子结点的值，根结点的值一定是所有结点中最小的
  - 按照层序遍历，给结点从1开始编号，则结点之间满足下面的关系,其中1<=i<=[n/2]:
- 按照层序遍历，将上图中的大顶堆存入数组中，小顶堆类似，如下图所示:
3.原理:首先，将待排序的n个元素构造成一个大顶堆(小顶堆也可以，下面以大顶堆为例)。此时，这个序列的最大值就是大顶堆的根结点；然后，将大顶堆的根结点与堆数组中的最后一个元素进行交换，交换后，大顶堆的根结点存放的就是堆数组中的最后一个元素，大顶堆的根结点中存储的原始的最大值被移走啦；接着，将剩下的n-1个元素重新调整后，构造成一个新的大顶堆，重复上面的步骤，被移动的元素就构成了一个有序的数据。下面解决两个问题:(1)怎么将一个无序的数据构造成一个大顶堆?;(2)怎么将剩余的元素重新调整，构成一个新的大顶堆?
4.动态过程

5.堆排序的完整代码

    #include <iostream>

    using namespace std;

    #define N 9
    #define MAXSIZE 10
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0

    typedef int Status;
    typedef struct{
        int r[MAXSIZE+1];
        int len;
    }Sqlist;

    void show(Sqlist L){
        for(int i = 1; i < L.len; i++)
            cout << L.r[i] << " ";
        cout << endl;
    }

    void Swap(Sqlist *L, int i, int j){
        int temp = L->r[i];
        L->r[i] = L->r[j];
        L->r[j] = temp;
    }
    // 堆排序需要考虑的两个问题：
    /*
        1.如何将一个无序的序列构造成一个大/小顶堆
        2.在输出堆顶元素后，怎么调整剩余的元素，使剩余的元素成为一个新的大/小顶堆
    */
    // 堆调整函数
    // 已知L->r[s..m]中的记录的关键字除L->r[s]之外均满足堆的定义，需要调整的关键字是L->r[s],使L->r[s...m]成为一个大顶堆
    void HeapAdjust(Sqlist *L, int s, int m){
        int temp, j;
        temp = L->r[s];  // L->r[s]是不满足大顶堆条件的结点，需要进行调整
        for(j = 2*s; j <= m; j*=2){  // 循环遍历当前结点s的左右孩子j，因为是完全二叉树，所以左孩子的序号是2*s，右孩子的序号是2*s+1
            if(j < m && L->r[j] < L->r[j+1])  // L->r[j]是左孩子,L->r[j+1]是右孩子,j<m说明当前的孩子结点不是完全二叉树的最后一个结点
                ++j;  // L->r[j] < L->r[j+1]说明左孩子小于右孩子,说明最大值在右孩子结点上
            if(temp >= L->r[j])  // 当前的结点s就是最大值，不需要调整，直接跳出循环
                break;
            L->r[s] = L->r[j];  // 将当前结点s与左右孩子结点j进行交换，调整成大顶堆
            s = j;
        }
        L->r[s] = temp;
    }

    // 下面的程序是以大顶堆为例！！！
    // 堆排序函数
    void HeapSort(Sqlist *L){
        int i;
        // 构建一个大顶堆,时间复杂度是O(n)
        for(i = L->len / 2; i >0; i--)  // 将L中的r[i]构造成一个大顶堆，i从L->len / 2开始是因为它们都是有左右孩子的结点
            HeapAdjust(L, i, L->len);
        // 重建一个大顶堆，时间复杂度是O(nlogn)
        for(i = L->len; i > 1; i--){    // 逐步将每个最大值的根结点与完全二叉树中的末尾元素进行交换，并且再调整使其成为一个新的大顶堆
            Swap(L, 1, i);   // 将大顶堆根结点与完全二叉树中最后一个元素交换，移除旧的大顶堆的根结点，现在剩余结点总数是i-1
            HeapAdjust(L, 1, i-1);  // 将L->r[1...i-1]重新调整为大顶堆，需要调整的元素索引是大顶堆的根结点1和剩余结点总数i-1
        }
    }



    int main(){
        Sqlist L;
        int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        for(int i = 0; i < N; i++)
            L.r[i+1] = d[i];
        L.len = N;
        cout << "堆排序前: ";
        show(L);
        cout << "堆排序后: ";
        HeapSort(&L);
        show(L);
        return 0;
    }

堆排序算法实现思想个人理解

相关推荐