第九章：排序

这是一个关于第九章：排序的思维导图，涵盖了排序的基本概念、内部排序的各类算法及其性质，适合用于课程学习、复习备考等场景，帮助读者深入掌握各类排序算法的原理、实现和性能特点。

第九章排序

• 内部排序
  • 直接插入排序
    • 直接插入排序（比较+移动+插入）［扑克牌思想］
      • 一个人从乱序的扑克牌中起牌的思想
      • 概念
        • 以最左侧第一个数作为开始的已排序序列（初始序列非空），从未排序序列中依次取出一个元素，与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置。
      • 算法思想
        • 人为的理解
          • ①以初始序列第一个数字为基础（n个关键字，需要插入n-1次） ②每次从初始序列依次加入的一个关键字到排序序列（选哨兵） ③按其大小插入到前面已排好序的子序列（比较+移动+插入） ④直到所有的关键字都插入成功为止
        • 计算机理解
          • ①（确定趟数）n个关键字，需要排n-1趟 ②（每趟给关键字设哨兵）每次将新选择的关键字放入哨兵位置，即数组下标为零的位置。 ③（每趟给关键字腾出合适位置）边比较，边移动。确保给新选择的这个关键字挪开了一个位置。 ④（将哨兵即此趟关键字放入刚刚腾出的位置）数组下标为零的值放入合适位置。 ⑤直到所有的关键字都插入成功为止
      • 算法过程
        • C语言版本
          • void insertsort（int a［］，int n） ｛ for（i＝1;i＜n;i++） ｛ a［0］＝a［i+1］; for（j＝i;a［j］＞a［0］;j--）a［j+1］＝a［j］; a［j+1］＝a［0］; ｝ ｝
        • 数据结构版本
          • void insertsort（sqlist &L） ｛ for（i＝1;i＜L.length;i++） ｛ L.r［0］＝L.r［i+1］; for（j＝i;L.r［j］.key＞L.r［0］.key;j--）L.r［j+1］＝L.r［j］; L.r［j+1］＝L.r［0］; ｝ ｝
      • 性能
        • 稳定性
          • 稳定
        • 时间复杂度
          • 最坏（序列原本逆序，既需要比较元素（比较 n（n-1）/2次），又需要移动元素）
          • 平均
          • 最好（序列原本有序，只需要比较元素（比较n-1次），不需要移动元素（移动0次））
        • 空间复杂度
        • 特殊记忆⭐️
          • ①序列基本有序时具有较好性能。 ②关键字记录n较小时具有较好性能。 ③在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上。 ④关键词比较次数最好（最少）：n-1次，最坏（最多）：n×（n-1）/2 ⑤对插入的第i个记录：最多比较i- 1，最少比较1次。
    • Shell希尔排序（分组+排序）［分组思想］
      • 本质上是直接插入排序，又称缩小增量排序
      • 算法思想
        • 增量序列（a，b，c）［增量序列最后一个必须是1，且是一个递减序列］ ①（确定趟数）增量序列的个数就是一共经历的趟数。（三趟） ②（每趟确定某个数字为分组原则）每趟以增量序列数字为分组原则进行分组，第n趟对应的分组原则的数字是增量序列第n个数字。（第一趟对应的分组原则数字是a，第二趟对应的分组原则数字是b，第三趟对应的分组原则数字是c） ③（每趟分组）从第一个数开始，将整个待排序数组分成增量序列每趟对应分组原则数字个组。待排序数组中第一个数对应的下标加上这一趟对应的分组原则的数字，待排序数组中第二个数对应的下标加上这一趟对应的分组原则的数字，以此类推，将加上分组原则数字得到的下标中对应的这几个数组成一个小组，得到的把整个序列分成a个组，b个组，C个组。 ④（每趟直接插入排序）对每趟中每组数据进行由小到大排序，各组排完序以后整体组合成一个新序列。 ⑤（重复②③④）直到经历完所有趟数，排序结束。
      • 算法过程
      • 性能
        • 稳定性
          • 不稳定
        • 时间复杂度
        • 空间复杂度
  • 交换排序
    • 冒泡排序（起泡排序）（比较+交换）［比较思想］
      • 算法思想
        • 人为理解
          • ①（确定趟数）有n个关键字，需要进行n-1趟排序。 ②（每次确定一个最小值到最左侧，边比较边交换）从后往前两两比较，如果是前大后小逆序就交换。 ③（整个序列按由小到大排序为止）直到每趟确定一个最小值到左侧，使得整个序列由小到大排序就结束。
        • 计算机理解
      • 算法过程
        • for（i＝0；i＜n-1；i++） ｛ for（j＝0；j＜n-1-i；j++） if（a［j］＞a［j+1］） ｛ t＝a［j］； a［j］＝a［j+1］； a［j+1］＝t； ｝ ｝
          • 从前往后图示
      • 性能
        • 稳定性
          • 稳定
        • 适用于
          • 顺序表和链表都可以
        • 时间复杂度
          • 最坏（序列原本逆序，比较次数＝交换次数＝n（n-1）/2）
          • 平均
          • 最好（序列原本有序，只需要比较n-1次，不需要交换元素）
        • 空间复杂度
      • 特殊记忆⭐️
        • ①元素完全逆序时比较的次数最多。 ②关键词比较次数最好（最少）：n-1次，最坏（最多）：n×（n-1）/2
    • 快速排序（类似折半查找）［选轴思想］
      • 算法思想
        • ①（选轴做哨兵）设置数组下标为一的元素为枢轴，并将其放入下标为零的元素做哨兵。 ②（设置low和high）low＝1，high＝被划分区间元素个数。 ③（high动：从后往前找比high小赋值给low）high：从后往前搜索，找到关键字比high大就继续找，直到找到比high小的关键字停止查找，将此关键字赋值给low。 ④（low动：从前往后找比low大赋值给high）low：从前往后搜索，找到关键字比low小就继续找，直到找到比low大的关键字停止查找，将此关键字赋值给high。 ⑤（low＝high）直到low和high相等为止。 ⑥（L.r［low］＝L.r［0］）把轴所在的零元素的值复制到low所指位置。
      • 算法过程
        • int partition（sqlust &L，int s，int t） ｛ pivotkey＝L.r［s］.key； L.r［o］＝L.r［s］； low＝1；high＝t； while（low＜high） ｛ while（low＜high&&L.r［high］.key＞＝pivotkey）--high； L.r［low］＝L.r［high］； while（low＜high&&L.r［low］.key＜＝pivotkey）++low； L.r［high］＝L.r［low］； ｝ L.r［low］＝L.r［0］； return low； ｝
      • 算法特点
        • 快速排序是所有内部排序算法中平均性能最优的排序算法。
      • 算法情况
        • 最好
          • 若每一次选中的“枢轴”将排序序列划分成均匀的两个部分，则递归深度最小，算法效率最高。
        • 最坏
          • 若每一次选中的“枢轴”将排序序列划分成很不均匀的两个部分，则递归深度增加，算法效率变低。
          • 若初始序列正序或逆序，则快速排序的性能最差。（因为每次选择的都是最边上的元素）
      • 性能
        • 稳定性
          • 不稳定
        • 时间复杂度
          • 最坏
          • 平均
          • 最好
        • 空间复杂度
        • 什么情况下效率最高？
          • ①被排序序列完全无序时具有较好性能。
  • 选择排序
    • 简单选择排序
      • 概念
        • 初始序列为空，从未排序序列中挑选元素，将其依次放入已排序序列的一端的方法称为选择排序
      • 算法思想
        • ①（确定趟数）n个数，需要排n-1趟。 ②（每趟选最小）每趟选择一个最小的数，与i位置数进行交换。
      • 算法过程
        • void selectsort （sqlist &L） ｛ for（i＝1；i＜L.length；i++） ｛ j＝i； for（k＝i+1；k＜L.length；k++） if（L.r［k］.key＜L.r［j］.key）j＝k； ｛t＝ L.r［i］； L.r［i］＝L.r.［j］； L.r.［j］； ｝ ｝ ｝
      • 性能
        • 稳定性
          • 不稳定
        • 时间复杂度
          • 最坏
            • • 需要交换n-1次，需要比较n（n-1）/2次
          • 平均
          • 最好
        • 空间复杂度
        • 关键字比较的次数与初始排列次序无关。 排序的时间复杂度不受待排序序列的影响。 需要交换n-1次，需要比较n（n-1）/2次
    • 堆排序
      • 堆分类
        • 大顶堆（大根堆）
          • 递增序列
          • 根结点（堆顶元素）为最大值
          • 每次建立一个大顶堆，将最大值确定在最右侧。
        • 小顶堆（小根堆）
          • 递减序列
          • 根结点（堆顶元素）为最小值
          • 每次建立一个小顶堆，将最小值确定在最右侧。
      • 判断是大小堆方法
        • 大顶堆（根≥左，右）
          • ①将线性序列按照从左到右的顺序画出一个完全二叉树。 ②检查每一个分支结点，如果每一个分支结点（根节点）≥左孩子且≥右孩子，则是大顶堆。
        • 小顶堆（根≤左，右）
          • ①将线性序列按照从左到右的顺序画出一个完全二叉树。 ②检查每一个分支结点，如果每一个分支结点（根节点≤左孩子且≤右孩子，则是小顶堆。
      • 建立大小堆的方法
        • 大顶堆（根≥左，右）
          • ①（画完全二叉树）将线性序列按照从左到右的顺序画出一个完全二叉树。 ②（检查根结点）从下往上检查每一个分支结点，确保每一个分支结点（根节点）≥左孩子且≥右孩子。 ③（不满足则让根结点与最大孩子交换）如果不满足②，则将此分支节点和他最大的孩子进行交换。 ④（再次复查）从下往上检查一遍根结点以后，再次检查有没有不符合②的，进行二次更改。
        • 小顶堆（根≤左，右）
          • ①（画完全二叉树）将线性序列按照从左到右的顺序画出一个完全二叉树。 ②（检查根结点）从下往上检查每一个分支结点，确保每一个分支结点（根节点）≤左孩子且≤右孩子。 ③（不满足则让根结点与最大孩子交换）如果不满足②，则将此分支节点和他最大的孩子进行交换。 ④（再次复查）从下往上检查一遍根结点以后，再次检查有没有不符合②的，进行二次更改。
      • 算法思想
        • ①（画完全二叉树）将线性序列按照从左到右的顺序画出一个完全二叉树。 ②（检查根结点）从下往上检查每一个分支结点，确保每一个分支结点（根节点）≥左孩子且≥右孩子。 ③（不满足则让根结点与最大孩子交换）如果不满足②，则将此分支节点和他最大的孩子进行交换。 ④（再次复查）从下往上检查一遍根结点以后，再次检查有没有不符合②的，进行二次更改。 ⑤（最右侧确定第一最大）直到此时的完全二叉树是一个大顶堆，然后把此大顶堆写成一个线性序列，将大顶堆的根结点即最左侧结点与最右侧的元素进行交换，在最右侧确定一个最大值。 ⑥（重复①②③④⑤）把除了最后一个元素的前面元素再次进行构建大顶堆。直到元素从最大到第二大到第三大依次都已确定为止
      • 性能
        • 稳定性
          • 不稳定
        • 时间复杂度
          • 最坏
          • 平均
          • 最好
        • 空间复杂度
  • 归并排序
    • 二路归并
      • 二合一
    • 概念
      • 归并
        • 把两个或多个有序序列归并成一个有序序列
      • 二路归并
        • 二合一
    • 算法思想
      • ①（两两为一小组）从左到右，将数据两两一组分成若干小组，组内分别进行排序。 ②（两两组为一大组）从左到右，将①中排好序的两两组为一大组分成若干大组，组内进行二次排序。 ③（两两大组为一大大组）从左到右，将②中排好序的两两大组为一大大组分成若干组，组内进行三次排序。 ④重复以上步骤，直到所有的数据都有序为止。
    • 算法过程
    • 性能
      • 稳定性
        • 稳定
      • 时间复杂度
        • 最坏
        • 平均
        • 最好
      • 空间复杂度
        • • 要求内存最大❤️
      • 趟数
• 基本概念
  • 定义
    • 将各关键字按照递增（正序）／递减（逆序）顺序进行重新排列
  • 分类
    • 按照关键字顺序
      • 正序：由小到大（关键字由小到大，即是递增的有序序列称为正序序列）
      • 逆序：由大到小（关键字由大到小，即是递减的有序序列，称为逆序序列）
    • 按照占内存大小
      • 内部排序：只涉及内存 （如果内存可以容纳所有待排序记录，排序过程只涉及内存，这种排序称为内部排序）
      • 外部排序：数据不光需要内存，而且必须借助外存 （待排序记录很多以至于内存无法容纳全部记录，必须借助于外存进行排序，这种排序称为外部排序）
  • 性能
    • 稳定性
      • 稳定
        • 一种排序方法可以保证关键字相同的记录在排序前后的相对次序保持不变
      • 不稳定
        • 一种排序方法使得关键字相同的记录在排序前后的相对次序发生改变
    • 时间复杂度
    • 空间复杂度