【数据结构】排序：选择排序（简单选择排序、堆排序等）详解与实现（C++）

客官°小女子只卖身不卖艺 2021-12-10 00:19 293阅读 0赞

\#笔记整理

***内部排序分类目录：***  
*- [插入排序][Link 1]  
\- [交换排序][Link 2]  
**-[\->选择排序][-]**  
\- [归并排序][Link 3]  
\- 计数排序*

# 选择排序 #

基本思想：每一趟 (第 i 趟，i = 0, …, n-1) 在后面 n - i 个待排序记录中选出关键字最小的记录, 作为有序序列的第 i 个记录。

#### 简单选择排序（Simple Selection Sort） ####

通过  n − i − 1 n - i - 1 n−i−1 次关键字间的比较，从  n − i n-i n−i 个记录中选取关键字最小的记录，并和第  i i i 个记录交换。

算法实现：

// 简单选择排序法，对容器nums进行排序
        void sSelectionSort(vector<int> &nums){
        
            int len = nums.size();
            for(int i = 0; i < len - 1; i++){
        
                int currMinIndex = i;                 // 最小记录的下标
                for(int j = i + 1; j < len; j++ ){
        
                    if(nums[j] < nums[currMinIndex]){
        
                        currMinIndex = j;
                    }
                }
                swap(nums[i], nums[currMinIndex]);    // 将最小记录与当前记录nums[i]进行交换。
            }
        }

[github源码][github]

![在这里插入图片描述][20190803134935483.png]

**简单选择排序是一种不稳定的排序方法，如对\{2, 2’, 1\}排序。**

冒泡排序法与选择排序法相比，一个从局部入手减少逆序元素，一个放眼大局逐个选择最小值，二者思路大不相同，但是，它们又都有着 “通过 i 次外层循环，从数据中顺次求出 i 个最小值” 的相同特征。

#### 堆排序（Heap Sort） ####

**堆**是具有下列性质的 **完全二叉树**：  
当每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。  
当每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

而堆排序算法是把顺序存储的数据看成是一棵**完全二叉树**，利用堆进行排序的方法。  
**基本思想：**  
对一组待排序记录的关键字，首先把它们按堆的定义建成小(大)顶堆，然后输出堆顶的最小(大)关键字所代表的记录，再对剩余的关键字建堆，以便得到次小(大)的关键字，如此反复进行，直到全部关键字排成有序序列为止。

**堆排序比较难理解，我简述一下实现流程：**

1.  将 nums 里的记录按照下标画成一课完全二叉树，可以看到树的内部结点的下标为 \[0, len/2 -1\] ( len 为nums中的记录个数)。
2.  遍历每一个内部结点，将其看成子堆的根结点，调整该子堆为大顶堆，最终整个nums为一个大顶堆。
3.  使用调整好的大顶堆进行排序，从后往前排，每次取出大顶值放到 nums 后面，然后调整剩下的为新的大顶堆。
4.  最终 nums 从后往前分别是 最大值到最小值，排序结束。

其中步骤 2 和步骤 4 需要使用到堆调整函数，该函数的实现流程简述如下：

*  先暂存下堆顶结点到一个变量 temp 中；
 *  遍历 temp 的所有子结点，找到最大的子结点，放到堆顶，即该子节点与 temp 交换位置；
 *  重复上一步，temp 遍历它的新子节点，直到找到自己应插入的位置。

**算法实现：**

// 堆排序法，对容器 nums 进行排序
        void heapSort(vector<int> &nums){
        
            int len = nums.size();
            int i;
            for(i = len / 2 - 1; i >= 0; i--){
                              // 从最后一个非叶子子结点到[0]，即 0 ~ [len/2 - 1] 都是非叶子结点。将这些分叶子结点看成子树(子堆)，分别进行调整
                heapAdjust(nums, i, len - 1);                       // 调整 nums[i]，nums[i ~ len-1] 成为大顶堆
            }
    
            for(i = len - 1; i > 0; i--){
                                   // -- 大顶堆创建完成，开始排序。排序过程为从后往前排，不断将大顶堆的顶部记录放到容器后面，然后调整前面的记录保持为大顶堆。
                swap(nums[0], nums[i]);                             // 交换堆顶记录[0]和未完全排序的nums[1 ~ i]中的最后一个记录[i]
                heapAdjust(nums, 0, i - 1);                         // 调整 nums[0]，使 num[0 ~ i-1]重新成为大顶堆
            }
        }
        // 堆排序法的堆调整函数，已知 nums[low ~ high] 中的记录除 nums[low]之外均满足大顶堆的定义，
        // 向下调整 nums[low]， 使 nums[low ~ high] 中记录均满足大顶堆的定义
        void heapAdjust(vector<int> &nums, int low, int high){
        
           int temp = nums[low];                                    // 利用临时变量存储待调整数据
           for(int j = 2 * low + 1; j <= high; j = 2 * j + 1){
              // j 指向 nums[low] 的左孩子，沿值较大的孩子结点向下筛选(因为下标从0开始，所以结点i的左孩子为2i+1)
                 // 该 for 循环的目的是找到以当前 nums[low] 为根结点的子树(子堆)中的最大值，再将此最大值和 nums[low]交换。
               if( j < high && nums[j] < nums[j + 1]){
                      // 左孩子小于右孩子
                    j++;                                            // j 为值较大的记录的下标，即 j 指向[low]的右孩子
               }
               if(temp >= nums[j]){
                                         // nums[low]的值大于或等于左右子树的值
                    break;                                          // 不必再调整，跳出for循环
               }
               nums[low] = nums[j];                                 // 否则，nums[j]为当前最大值，将它上移插入nums[low]的当前位置
               low = j;                                             // 同时 nums[low] 下移到 nums[j] 处，因为还需将它与剩下的结点作比较。
           }
           nums[low] = temp;                                        // 最终找到 temp 应插入的位置，将其插入nums[low]
        }

[github源码][github]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
**堆排序是一个不稳定的排序方法。**

#### 树形选择排序（锦标赛排序） ####

**算法思路：**  
n 个记录的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个记录再进行关键字的两两比较，…，如此重复，直到选出一个关键字最小的记录为止。  
（此算法用的不多，实现暂时略过，以后有时间再补充）  
![在这里插入图片描述][20190714224527740.png]  
**锦标赛排序是一个稳定的排序方法。**

部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆

[Link 1]: https://steve.blog.csdn.net/article/details/95931848
[Link 2]: https://steve.blog.csdn.net/article/details/95934166
[-]: https://steve.blog.csdn.net/article/details/95935599
[Link 3]: https://steve.blog.csdn.net/article/details/96337444
[github]: https://github.com/yohstone/data-structure/blob/master/sort.cpp
[20190803134935483.png]: /images/20211209/f04a1e023ace4e96b496ec28c205c58b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211209/532333e6639c4499beb45ba7b6777362.png
[20190714224527740.png]: /images/20211209/11e73bea5c8a49578220d2feaba3c115.png