数据结构_C++语言描述_高教出版社-十、排序

10.1 排序的基本概念

关键字：

• 主关键字：每一个待排序的该关键字是独一无二的
• 次关键字：每一个待排序的该关键字可能是重复的

稳定性：

• 场景：只针对次关键字的情况
• 稳定：按照次关键字排序后，原来相同关键字的顺序不变
• 不稳定：按照次关键字排序后，原来相同关键字的顺序可能会改变

内外排序：

• 内排序：数据全部存放在内存
• 外排序：数据量过大时，待排序的数据在内存与外存之间不断转换

10.2 冒泡排序

基于交换的思路进行

稳定的

10.3 选择排序

• 选择第 1 小的数放在第一个位置，…，选择第 i 小的数放在第 i 个位置

• 共选择 n-1 次

10.4 插入排序

• 直接插入排序：依次向前缀已经排好序的序列中进行插入 - $O(n^2)$
• 折半插入排序：同上，只是选择插入位置的使用二分 - $O(n\log n)$
• 递归插入排序：排序 [1,i] 等价于先排好 [1,i-1]，然后插入当前 num[i] 即可

稳定的

10.5 希尔排序

基于插入直接排序的优点：

1. 当序列基本有序时，效率很高
2. 当待排序数很少时，效率很高

于是希尔（Shell）就得出来以下的希尔排序算法：

1. 将序列划分一定次数，从 d<n 到 1
2. 每次划分都对组内的元素进行直接插入排序
3. 最后分为 1 组时，直接排序一趟以后就可以得到 sortrd sequence

不稳定

10.6 快速排序

分治法三步骤：divide、conquer and combine

每次选择一个 pivot 进行 partition，递归两个 partition

void Sort(int l, int r) {
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);            
    }
    
    Sort(l, j), Sort(j + 1, r);
}

不稳定

10.7 堆排序

堆与堆排序的定义

首先我们得知道什么是堆结构。堆是具有下面性质（对于任意的 $1\le i\le n/2$ ）的完全二叉树

• $k_i\le k_{2i}、k_i\le k_{2i+1}$ 叫做 小顶堆

• $k_i\ge k_{2i}、k_i\ge k_{2i+1}$ 叫做 大顶堆

因此一个堆结构可以采用线性的单元进行存储与维护

而堆排序利用堆顶是最值这一性质，通过不断的取堆顶，调整堆的方式获得最终的排好序的序列

建立初始堆

由于完全二叉树中，每一个叶子结点都已经是堆结构，因此直接从第一个非叶子结点开始建堆即可。对每一个元素与左孩子、 右孩子进行比较

• 如果当前结点的值比左右孩子都大，那么无需修改，当前位置就是堆顶
• 如果当前结点的值比左孩子或者右孩子中的最大值小，则将最大的孩子作为堆顶，并将当前值不断的“下沉”即可

交换堆顶与记录位置后重新建堆

交换记录值获取当前堆中最值以后，需要将除了已记录的值的结点以外的所有结点重新调整为堆结构

• 调整为堆结构的过程与上述初始建堆的过程完全一致，只是结点数每次 -1

时间复杂度 $O(n\log n)$

不稳定

10.8 归并排序

递归

同样采用分治法，我们按照分治法的三个步骤进行讨论

• divide: 将当前序列划分为左右两部分
• conquer: 递归处理上述划分出来的两部分
• combine: 归并上述递归完的两部分

时间复杂度 $O(n\log n)\leftarrow T(n)=2T(\frac{n}{2})+O(n)$

非递归

就是模拟上述递归的过程，可以拆分为三步

• 归并
• 按照指定的长度处理整个序列
• 划*部排序的长度

稳定的