堆排序算法——C/C++

刺骨的言语ヽ痛彻心扉 2022-01-17 10:05 229阅读 0赞

# 堆排序 #

## 1. 算法思想 ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

## 2. 实现原理 ##

要实现从小到大的排序，就要建立大顶堆，即父节点比子节点都要大。

2.1、初始化数组，创建大顶堆。
    	1. 大顶堆的创建从下往上比较，不能直接用无序数组从根节点比较，否则有的不符合大顶堆的定义。
    2.2、交换根节点和倒数第一个数据，现在倒数第一个数据就是最大的。
    2.3、重新建立大顶堆。
    	1. 因为只有 array[0] 改变，其它都符合大顶堆的定义，所以可以根节点 array[0] 重新建立。
    2.4、重复2.2、2.3的步骤，直到只剩根节点 array[0]，即 i=1。

## 3. 动态演示 ##

网上这个就展示的非常好  
![在这里插入图片描述][20190613001742222.gif]

我再用图片稍微解释一下。  
**原始数据：array\[\]=\{49,38,65,97,76,13,27,49,10\}**  
**原始堆排序**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]**创建大顶堆**  
从倒数第二行往上比较父节点和子节点（即从数据一半开始向前运算），把大的往上移动，小的向下移，直到符合大顶堆定义。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]**交换根节点和最后一个节点**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]  
**重新创建大顶堆**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]接下来就一直循环即可得到堆排序结果

## 4. 完整代码 ##

五个函数  
交换函数：void swap(int array\[\],int x,int y)  
初始化大顶堆函数：void BuildHeap(int array\[\],int size)  
生成大顶堆函数：void Down(int array\[\],int i,int n)  
排序函数：void heapSort(int array\[\],int size)  
主函数：int main()

#include <stdio.h>
    
    void display(int array[], int size) {
        
        for (int i = 0; i < size; i++) {
        
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    void swap(int array[], int x, int y) {
        
        int key  = array[x];
        array[x] = array[y];
        array[y] = key;
    }
    
    // 从大到小排序
    // void Down(int array[], int i, int n) {
        
    //     int child = 2 * i + 1;
    //     int key   = array[i];
    //     while (child < n) {
        
    //         if (child + 1 < n && array[child] > array[child + 1]) {
        
    //             child++;
    //         }
    //         if (key > array[child]) {
        
    //             swap(array, i, child);
    //             i = child;
    //         } else {
        
    //             break;
    //         }
    //         child = child * 2 + 1;
    //     }
    // }
    
    // 从小到大排序
    void Down(int array[], int i, int n) {
         // 最后结果就是大顶堆
        int parent = i;                    // 父节点下标
        int child  = 2 * i + 1;            // 子节点下标
        while (child < n) {
        
            if (child + 1 < n && array[child] < array[child + 1]) {
         // 判断子节点那个大，大的与父节点比较
                child++;
            }
            if (array[parent] < array[child]) {
         // 判断父节点是否小于子节点
                swap(array, parent, child);     // 交换父节点和子节点
                parent = child;                 // 子节点下标 赋给 父节点下标
            }
            child = child * 2 + 1; // 换行，比较下面的父节点和子节点
        }
    }
    
    void BuildHeap(int array[], int size) {
        
        for (int i = size / 2 - 1; i >= 0; i--) {
         // 倒数第二排开始, 创建大顶堆，必须从下往上比较
            Down(array, i, size);                 // 否则有的不符合大顶堆定义
        }
    }
    
    void HeapSort(int array[], int size) {
        
        printf("初始化数组：");
        BuildHeap(array, size); // 初始化堆
        display(array, size);   // 查看初始化结果
        for (int i = size - 1; i > 0; i--) {
        
            swap(array, 0, i); // 交换顶点和第 i 个数据
                               // 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
            Down(array, 0, i); // 重新建立大顶堆
    
            printf("排序的数组：");
            display(array, size);
        }
    }
    
    int main() {
        
        int array[] = {
        49, 38, 65, 97, 76, 13, 27, 49, 10};
        int size    = sizeof(array) / sizeof(int);
    
        // 打印数据
        printf("%d \n", size);
        printf("排序前数组：");
        display(array, size);
        HeapSort(array, size);
    
        return 0;
    }

## 5. 结果展示 ##

（显示每次排序结果）  
从小到大  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 4]从大到小  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 5]

## 6. 算法分析 ##

时间复杂度：

1.  最好：O(n log n)
2.  最坏：O(n log n)
3.  平均：O(n log n)

空间复杂度：O(1)

稳定性：不稳定

[20190613001742222.gif]: /images/20220117/7516f88e83f44ca28441f967b6b9ceca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20220117/d6700a0dec1f41e8bd4413c83bb02f1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20220117/0bcc399a7b6c4ed889452259c1062657.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: /images/20220117/fd11fab7bffb4b569554d464ec8611e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]: /images/20220117/26a166cca5794e01a4de550f023f526a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 4]: /images/20220117/6f0fddce51e447c8af3170cb732cb5df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 5]: /images/20220117/35074eb655fa401f9d44414b83ea8ff6.png