本文介绍各种排序算法。

0 排序算法总结

内部排序算法性能对比表（回忆高亮项原因）：

最快："快些归堆"

不稳定："快些选堆"

• 为了最终稳定，通常在选择复数不同稳定性的算法时，考虑先⽤不稳定的排再⽤稳定的排

内部排序重要性质总结：

1. 对于⽐较类排序（所有涉及到两两⽐较操作的排序），对任意n个关键字两两比较排序的最少比较次数为\left \lceil \log_2(n!) \right \rceil
2. 经过⼀趟排序，能够保证⾄少⼀个关键字到达最终位置的算法：交换类——冒泡、快排，选择类——选择、堆排
   • 插排类在最后⼀趟排序前，没有任何⼀个关键字到达最终位置
3. 排序算法的关键字⽐较次数与原始序列⽆关的算法：折半插入（折半查找判定树唯一）、选择（每趟都须完整遍历剩余序列）

待排序列存储⽅式的选择：

• 为了提⾼内部排序效率，待排序列应尽量使⽤顺序存储结构存储
• 若采⽤链式存储结构，将无法有效进行希尔排序与堆排序，因为这两种都利⽤了顺序表的随机存储特性

C++标准库<algorithm>排序函数std::sort(begin, end, cmp)、交换函数std::swap(a, b)

---

1 插入类排序

若直接出现“插⼊排序”，默认指的是直接插入排序

直接插入排序相当于增量为1的希尔排序

1.1 直接插入排序

算法思想：每次排序将⼀个待排记录插⼊前⾯的有序⼦序列中

1. 顺序查找L[i]在有序子序列L[1...i-1]中的插入位置k
2. 将L[k...i-1]中所有元素依次后移一位
3. 将L[i]复制到L[k]

特点：

• 在n-1趟排序中，每趟操作分为⽐较关键字和移动元素，两者都取决于待排序表的初始状态
• 第i轮排序中，区间[1,i-1]内元素有序
• 稳定性：稳定

效率分析：

• 时间效率
  • 最好情况：表中元素初始有序，此时每次只需⽐较1次元素⽽⽆需移动，T_{\text{best}}(n)=O(n)
  • 最坏情况：表中元素初始逆序，此时n个关键字的排序要比满\dfrac{n(n-1)}{2}次，T_{\text{worst}}(n)=O(n^2)
  • 平均情况：T_{\text{avg}}(n)=O(n^2)
• 空间效率：S(n)=O(1)

/* 简洁实现，元素存储于[0, L.length - 1] */
void insertSort(SqList &L) {
    for (int i = 1; i < L.length; i++)
        for (int j = i; j >= 1 && L.data[j] < L.data[j - 1]; j--)
            swap(L.data[j], L.data[j - 1]);
}

/* 使⽤“哨兵”，元素存储于[1, n] */
void insertSort(ElemType A[], int n) {
    for (int i = 2; i <= n; i++) {  // 从第⼆个元素开始遍历待排元素
        if (A[i] < A[i - 1]) {  // 若当前元素逆序（⼩于前驱）则需寻找插⼊位置
            A[0] = A[i];    // 哨兵寄存待排元素
            int j;  // 记录插⼊位置，即为不⼤于哨兵的元素之后
            for (int j = i - 1; A[0] < A[j]; j--) { // 往前寻找第⼀个不⼤于哨兵的元素
                A[j + 1] = A[j];    // 元素后移
            }
            A[j + 1] = A[0];    // 最终应在该元素之后插⼊
        }
    }
}

1.2 折半插入排序

算法思想：对插排中第1步"查找"操作进行改进，使⽤折半查找代替顺序查找，其余不变

特点：

• ⽐较次数与待排序表初始序列⽆关，仅取决于表⻓n；⽽元素的移动次数仍取决于排序表初始状态
• 稳定性：稳定
• 适⽤性：仅适⽤于顺序存储（同折半查找），适合关键字数较多的场景

效率：

• 时间效率：T_{\text{best}}(n)=O(n\log n)，T_{\text{worst}}(n)=O(n^2)，T_{\text{avg}}(n)=O(n^2)（主要取决于折半查找）
• 空间效率：S(n)=O(1)

/* 使⽤"哨兵"，元素存储于[1, n] */
void biInsertSort(ElemType A[], int n) {
    for (int i = 2; i <= n; i++) {  // 从第⼆个元素开始遍历待排元素
        A[0] = A[i];    // 哨兵寄存待排元素
        int low = 1, high = i - 1;  // ⼆分查找区间：有序子区间[1, i-1]
        while (low <= high) {   // 折半查找待插位置low（upper_bound）
            int mid = (low + high) / 2;
            if (A[mid] > A[0]) high = mid - 1;
            else low = mid + 1;
        }
        for (int j = i - 1; j >= low; j--) {    // 将待插位置low及以后元素后移⼀位
            A[j + 1] = A[j];
        }
        A[low] = A[0];  // 在待查位置low处插⼊待排元素
    }
}

1.3 希尔排序

算法思想：

1. 根据某⼀增量d序列，将待排序表分割为若干段特殊子表L[i, i+d, i+2*d, ..., i+k*d]
2. 每轮迭代将增量d减半（或使用特殊序列），对上述⼦表分别进⾏直接插⼊排序
3. 规定最后一轮d必为1，此时相当于对全体记录进⾏⼀次直接插⼊排序

特点：

• 增量d序列最后一个值必为1，增量值应尽量没有1以外的公因⼦
• 稳定性：相同关键字的记录可能被划分到不同⼦表中，故希尔不稳定
• 适⽤性：仅适⽤于顺序存储

效率：

• 时间效率：增量折半递减时T(n)=O(n^2)；增量序列为2^{k}+1,\cdots,17,9,5,3,1时T(n)=O(n^{1.5})
• 空间效率：S(n)=O(1)

/* 简洁实现，元素存储于[0, L.length - 1] */
void shellSort(SqList &L) {
    for (int d = L.length / 2; d >= 1; d /= 2)
        for (int i = d; i < L.length; i++)
            for (int j = i; j >= d && L.data[j] < L.data[j - d]; j--)
                swap(L.data[j], L.data[j - d]);
}

/* 使⽤“哨兵”，元素存储于[1, n] */
void shellSort(ElemType A[], int n) {
    for (int d = n / 2; d >= 1; d /= 2) {   // 从下一行起，直接将插排中的<code>1</code>改为<code>d</code>
        for (int i = 1 + d; i <= n; i++) {  // 遍历各⼦表
            if (A[i] < A[i - d]) {
                A[0] = A[i];
                int j;
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) { // 注意需保证下标j⼤于0
                    A[j + d] = A[j];
                }
                A[j + d] = A[0];
            }
        }
    }
}

---

2 交换类排序

若直接出现“交换排序”，默认指的是起泡排序（冒泡排序），本文仅介绍其单交换型

2.1 起泡排序

算法思想：

1. 每次排序从后往前两两⽐较相邻元素的值，若为逆序则交换
2. 每趟必将⼀个最⼤值移⾄序列末端，⾄多需进⾏n-1

特点：

• 每趟必有⼀个元素到达最终位置，有序⼦序列必定是全局有序的
• 稳定性：稳定

效率：

• 时间效率：
  • 最好情况：序列从⼩到⼤有序，T_{\text{best}}(n)=O(n)
  • 最坏情况：序列从⼤到⼩逆序，T_{\text{worst}}(n)=O(n^2)
  • 平均情况：T_{\text{avg}}(n)=O(n^2)
• 空间效率：S(n)=O(1)

void bubbleSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {   // n个元素最多进⾏n-1次冒泡
        bool flag = false;  // 记录冒泡过程中有⽆元素交换
        for (int j = n - 1; j > i; j--) {   // 从后往前⽐较
            if (A[j - 1] > A[j]) {
                swap(A[j - 1], A[j]);
                flag = true;
            }
        }
        if (!flag) return;  // 未进⾏交换即表示排序已完成，可以选择直接提前退出
    }
}

2.2 快速排序

算法思想：

1. 在待排序列L[low...high]中选择⾸元素L[low]或尾元素L[high]元素作为枢轴pivot；双指针i、j位于序列两端
2. 进⾏【划分】操作：轮流执⾏以下循环，当双指针i、j相遇时立刻结束循环——
   • 右侧元素应⼤于等于枢轴，此时j一直走，直⾄不满⾜条件，则将当前元素赶⾄i处
   • 左侧元素应小于等于枢轴，此时i一直走，直⾄不满⾜条件，则将当前元素赶⾄j处
     

     枢轴在哪边，就从另⼀边开始

3. 最终双指针相遇于i处，这⼀趟划分将待排序列分为L[low...i-1]、L[i+1...high]两段，枢轴pivot则放在最终位置L[i]上
4. 递归处理待排子序列

特点：

• 每趟必有⼀个元素（枢轴）到达所划分的最终位置，且满⾜左⼩右⼤
• 推⼴——快排的阶段性排序特点：第i趟完成时，会有i个以上的数出现在它最终将要出现的位置且满⾜左⼩右⼤
• 最大递归深度为n，最小递归深度为\left \lfloor \log_2 n \right \rfloor +1
• 稳定性：相同关键字容易被划分到不同区间，故快排不稳定

【总结与归纳】快排性质的应⽤

1. 判定序列为快排其中⼀趟的⽅法：根据快排的阶段性特点，若序列的明显有序元素（左⼩右⼤）的个数⼩于理论下限（当前排序趟数），则必定不是快排
2. 递归快排中递归次数与何有关？
   • 递归次数与各元素的初始排列有关（划分后分区⽐较平衡，则递归次数少；划分后分区不平衡，则递归次数多）
   • 递归次数与左右分区的处理顺序⽆关

效率：

• 时间效率
  • 最好情况：待排序列越乱越快，T_{\text{best}}(n)=O(n\log n)
  • 最差情况：序列接近有序时效率奇低，T_{\text{worst}}(n)=O(n^2)
  • 平均情况：T_{\text{avg}}(n)=O(n\log n)，最⾼次项系数最⼩，故在同级别算法中平均性能最好
• 空间效率：S(n)=O(n\log n)，递归使⽤了系统栈

/* 划分操作 */
int partition(ElemType A[], int low, int high) {    // 双指针初始位于两端
    ElemType pivot = A[low];    // 此处令枢轴为开始元素
    while (low < high) {    // 枢轴在哪边，就从另⼀边开始
        while (low < high && A[high] >= pivot) high--;  // 右⼤：右侧元素应⼤于等于枢轴
        A[low] = A[high];   // 不满⾜则赶去左边
        while (low < high && A[low] <= pivot) low++;    // 左⼩：左侧元素应⼩于等于枢轴
        A[high] = A[low];   // 不满⾜则赶去右边
    }
    A[low] = pivot; // low即为枢轴的最终位置
    return low;
}

/* 对A[low...high]进行快排 */
void quickSort(ElemType A[], int low, int high) {
    if (low < high) {   // low⼩于high才有意义
        int pivotPos = partition(A, low, high); // 划分数组，确认枢轴位置
        quickSort(A, low, pivotPos - 1);    // 递归排序枢轴左侧
        quickSort(A, pivotPos + 1, high);   // 递归排序枢轴右侧
    }
}

---

3 选择类排序

若直接出现“选择排序”，默认指的是简单选择排序，在本文中一律从前往后选择（最小值）

3.1 简单选择排序

算法思想：

• 共进⾏n-1趟排序，第i趟中的操作为从L[i...n]中选择关键字最小的元素L[minIdx]，将其替换至L[i]的位置，存在两种方式——
  • 插入：L[i...minIdx-1]上的元素集体后移一位（参考线性表的插入操作）。基于插入的简单选择排序是稳定的，但当查找表为顺序表时需进行大量操作，不可取，仅当查找表为链表时较为适合。
  • 交换：L[minIdx]直接与L[i]交换（Swap）位置。基于交换的简单选择排序是不稳定的，但非常适合顺序存储的查找表（随机存取）。一般情况下数据结构中所指的简单选择排序均是指基于交换的版本（本文亦仅给出该版本的代码）。

特点：

• 排序趟数固定为n，即元素移动次数为O(n)
• 稳定性：基于交换的选择排序是不稳定的，但基于插⼊的选择排序是稳定的

效率：

• 时间复杂度：T(n)=O(n^2)
• 空间复杂度：S(n)=O(1)

void selectSort(ElemType A[], int n) {
    for (int i = 0; i < n; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIdx]) {
                minIdx = j;
            }
        }
        swap(A[i], A[minIdx]);
    }
}

3.2 堆排序

堆（Heap)：⼀种结点值特殊排列的完全⼆叉树，根据⽗结点与⼦结点的数据⼤⼩关系可以分为——

• 大根堆（Max Heap）：H[父] >= H[子]
• 小根堆（Min Heap）：H[父] <= H[子]

存储结构：通常使⽤⼆叉树的孩⼦存储结构（顺序存储结构），关键字存储范围为[1,n]，长度仍为n

堆排序算法思路：

1. 初始化堆：先从最后⼀个⾮叶结点\left \lfloor \dfrac{n}{2} \right \rfloor起往前迭代建⽴⼤根堆
2. 调整（筛）：每轮转换将堆顶（最⼤值）与⽆序序列最后⼀个元素交换，然后调整之前元素为堆

特点：

• 第i轮排序后，前n-1个记录无序，后i个记录有序
• 稳定性：向下筛选时可能会把后⾯的相同关键字调整到前⾯，故堆排不稳定
• 适⽤性：最适合关键字数量极多的情况，亦非常适合进行局部排序——只需求出其中最⼤的若⼲元素

效率：

• 时间复杂度：T(n)=O(n\log_2 n)
• 空间复杂度：S(n)=O(1)

/* 向下调整根为k号结点、⻓度为n的⼦树为⼤顶堆 */
void downAdjust(ElemType H[], int k, int n) {
    for (int i = 2 * k; i <= n; i *= 2) {   // 左孩⼦：2*k，右孩⼦：2*k+1
        if (i + 1 <= n && H[i + 1] > H[i]) i++; // 选取左右孩⼦较⼤的那个（若存在）

        if (H[i] < H[k]) {  // 若孩⼦⽐⽗亲⼤则交换，指向⽗亲的索引k下移
            swap(H[k], H[i]);
            k = i;
        } else break;   // 否则表明调整结束
    }
}

/* 初始化⼤顶堆 */
void buildMaxHeap(ElemType H[], int n) {
    for (int i = n / 2; i >= 1; i--) {  // 建⼤顶堆：从最后⼀个⾮叶结点(n/2)开始向下调整
        downAdjust(H, i, n);
    }
}

/* 堆排序主函数 */
void heapSort(ElemType H[], int n) {
    buildMaxHeap(H, n);
    for (int i = n; i >= i; i--) {
        swap(H[1], H[i]);   // 将堆顶与当前⽆序序列最后⼀个元素i交换，使得最后⼀个元素i有序
        downAdjust(H, 1, i - 1);    // 随后再向下调整⽆序序列内 i-1 个元素
    }
}

3.2.A 维护映射关系的堆*

若无此需求，实际应用中可直接使用std::priority_queue<int>快速实现，默认为大根堆，可自定义比较规则以实现小根堆（更常用），高效查找最小值：

priority_queue<int> max_heap;  // 默认为大根堆
priority_queue<int, vector<int>, greater<int> > min_heap;  // 小根堆

首先介绍另一种更简洁的数组堆实现方式（此处以小根堆为例），元素存储范围同样为[1, n]。尽管该种写法在向下调整操作中使用了递归，增加了空间复杂度，但易读易懂易写，大幅提升了编码效率，在各类考试竞赛中更为常用：

int h[N], n;
// h[1 ... n]为小根堆，h[1]为堆顶/最小值，结点u的双亲为u/2，左右孩子分别为2*u、2*u+1（若存在）

/* 向下调整：一路向下交换结点u与其较小的儿子（递归） */
void down(int u) {
    int t = u;  // 记录u、2u、2u+1三个结点中的最小值结点编号
    if (u * 2 <= n && h[u * 2] < h[t]) {
        t = u * 2;
    }
    if (u * 2 + 1 <= n && h[u * 2 + 1] < h[t]) {
        t = u * 2 + 1;
    }

    if (u != t) {
        swap(u, t);
        down(t);
    }
}

/* 向上调整 */
void up(int u) {
    while (u / 2 && h[u] < h[u / 2]) {
        swap(u, u / 2);
        u /= 2;
    }
}

/* O(n)建堆 */
for (int i = n / 2; i; i--) {
    down(i);
}

通过新增两种映射数组——表中序号至堆中下标ph[N]（Position-Heap）、堆中下标至表中序号hp[N]（Heap-Position），可实现堆中任意元素的插入删除操作，并建立与原始插入序列之间的映射关系（以下继续以小根堆为例）：

int h[N], cnt;
int ph[N], hp[N], idx;
// h[1 ... cnt]为小根堆：h[1]为堆顶/最小值，结点u的双亲为u/2，左右孩子分别为2*u、2*u+1（若存在）
// ph[k]映射插入序列中第k个点到堆中的下标u
// hp[u]映射堆中结点u到插入序列中的序号k

/* 堆swap函数：交换堆中两个结点a和b的所有信息（若不建立映射则用std::swap()即可） */
void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

/* 向下调整：一路向下交换结点u与其较小的儿子 */
void down(int u) {
    int t = u;  // 记录u、2u、2u+1三个结点中的最小值结点编号
    if (2 * u <= cnt && h[2 * u] < h[t]) {
        t = 2 * u;
    }
    if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) {
        t = 2 * u + 1;
    }

    if (t != u) {
        heap_swap(u, t);
        down(t);
    }
}

/* 向上调整：一路向上交换结点u与其父结点 */
void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        heap_swap(u / 2, u);
        u >>= 1;
    }
}

/* 插入一个数x */
void insert(int x) {
    cnt++, idx++;
    ph[idx] = cnt;
    hp[cnt] = idx;
    h[cnt] = x;
    up(cnt);
}

/* 删除最小值/堆顶元素 */
void remove_top() {
    heap_swap(1, cnt);
    cnt--;
    down(1);
}

/* 删除第k个插入的元素 */
void remove(int k) {
    int u = ph[k];
    heap_swap(u, cnt);
    cnt--;
    up(u);  // 只会执行其中一个
    down(u);
}

/* 修改第k个插入的元素为x */
void change(int k, int x) {
    int u = ph[k];
    h[u] = x;
    up(u);  // 只会执行其中一个
    down(u);
}

3.B 对顶堆*

C++实现：使用两个multiset（std::multiset），上大下小。上下堆的大小差应时刻保持不超过1。

应用：快速查询有序序列的中位数，中位数从属于哪个堆与元素数为偶数（n=2k）时取孰为中位有关：

• 通常取中位为\dfrac {n}2，则中位处于较小的下堆。此时下堆大小可以比上堆多1。
• 取\dfrac n2+1时，各种情形与上述相反

---

4 归并排序

二路归并算法思路：类似线性表的⾮递减归并操作，每层归并时，在两段待归并序列中选择最⼩值并⼊新⼦序列

特点：

• 稳定性：稳定
• 对n个元素进行k路归并排序，设排序趟数为x，则有k^x=n，故排序趟数为\left \lceil \log_k n \right \rceil
  • 特别地，二路归并的排序趟数为\left \lceil \log_2 n \right \rceil
• 排序过程中⽐较次数与序列初始状态⽆关

效率：

• 时间复杂度：T(n)=O(n\log n)
• 空间复杂度：S(n)=O(n)，使用了辅助数组

/* 尾递归⼆路归并A[low...high] */
void mergeSort(ElemType A[], int low, int high) {
    if (low >= high) return;

    int mid = (low + high) / 2;
    mergeSort(A, low, mid); // 递归归并左半序列（中点mid划归左半序列）
    mergeSort(A, mid + 1, high);    // 递归归并右半序列

    ElemType temp[high - low + 1];  // 辅助数组（⻓度同待归并序列）记录归并后的新⼦序列
    int k = 0, i = low, j = mid + 1;    // k: 新⼦序列；i、j: 遍历两段待归并序列（皆为闭区间）
    while (i < mid && j <= high) {
        if (A[i] < A[j]) temp[k++] = A[i++];
        else temp[k++] = A[j++];
    }
    while (i <= mid) temp[k++] = A[i++];
    while (j <= high) temp[k++] = A[j++];

    for (int i = low, j = 0; i <= high; i++, j++)
        A[i] = temp[j]  // 将归并后的新⼦序列注⼊原序列
}

---

5 基数排序

基数排序（Radix Sort）：不基于⽐较和移动，⽽是借助多关键字排序思想，基于各位⼤⼩，对具有d位的单关键字进⾏排序。

排序⽅法：

1. 最⾼位优先（MSD）：从键值最⾼位 → 最低位排序、分组
2. 最低位优先（LSD）：与MSD相反，从键值最低位 → 最⾼位排序、分组

算法思路：

• 桶（Bucket）：基数排序的核⼼容器（故又常称为桶排序），数据结构为队列。
• 基（Radix）r：关键字某位范围的大小（例如数字0~9，r=10），即桶的数量。各桶根据代表的数字从左⾄右递增顺序摆放。
• 排序过程：此处以LSD为例，从低位最低位⾄最⾼位（位数不⾜则在⾼位补0）进⾏d轮迭代（d为关键字位数，决定循环次数），每轮执行以下两步操作——
  1. 【分配】：按关键字某位将各元素放⼊对应的桶
  2. 【收集】：从左⾄右使桶内元素依次出队，从左往右依次排列

性能分析：平均和最差情况下都有T(n)=O(d(n+r)),S(n)=O(r)，其中

• n：序列中关键字数
• d：关键字位数
• r：关键字基数（构成关键字的符号），即桶的数量

注：基数排序的时间复杂度与数组是否排序⽆关

---

6 外部排序

外部排序核⼼思想：将内存作为⼯作空间辅助外存排序

基本算法：k路归并排序

• 排序过程（图为⼆路归并（k=2）的过程）：
  1. 【分段】：将待排数据划分成m个小记录段，写入内存进行排序（方法任选）再写回外存，每个有序记录段称为归并段（顺串）
     
  2. 【分组】：将所有归并段每k段分为一组（k路），对每一组进行【归并】：读入k个关键字（每⼀路读⼊⼀个），挑出最⼩值写入外存，同时内存中补上对应路的下一个关键字
     
  3. 对【归并】所得的⼤归并段继续执⾏【分组】【归并】，反复循环最终可实现排序
     
• 基本算法特点（缺点）：
  • 全过程需要使⽤k个内存空间
  • 每次归并需要\text{2}次I/O操作（读、写各1次）

重要⼦算法：针对缺点进行改进

1. 置换-选择排序
   • 改进思想：优化【分段】过程。⽆需⼿动分段，可⾃适应任意⼤⼩的内存空间（缓冲区）
   • 改进后的分段过程：
     1. 将n个记录依次缓缓填⼊内存，直⾄缓冲区满
     2. 选出缓冲区中的最⼩值，并作如下【判断】：
        • 若⼤于既得有序段的最新值则写回外存，外存记录段填补其空
        • 否则⽆视并标记之，从缓冲区剩余记录中继续选出最⼩值，继续此【判断】
     3. 当排序⽆法继续进⾏时（缓冲区所有记录都被标记或⽆剩余记录），视为⼀趟排序结束，获得了⼀段归并段。
     4. 若缓冲区仍有被标记记录，则抹去标记，重复第2步操作开始新⼀轮排序。最终可⽣成若⼲⻓度不等的归并段
2. 最佳归并树
   • 改进思想：优化【分组】过程。找出最佳分组，使I/O总次数（【归并】次数）最少
   • 重要概念：
     1. 归并树：反映归并过程的树。叶结点表示初始归并段，权值为该归并段⻓度，边表示归并操作。\text{I/O总次数}=\sum w\cdot l，即为带权路径长度。
     2. 最佳归并树：I/O总次数最少，即带权路径最短（哈夫曼树！）
   • 建树⽅法：⽤构造哈夫曼树的⽅式建树（详见“哈夫曼树与哈夫曼编码”）
3. 败者树：较难，了解即可
   • 改进思想：优化选择缓冲区内最⼩值的⽅法，减少⽐较次数
   • 建树⽅法：
     1. 叶结点（记录，关键字）排成⼀列并编号，⽤各结点编号的值构造各⾃的⽗结点，⽣成若⼲棵树
        • 即使经历后续【合并】操作，这些父结点始终直接连接初始对应编号的叶结点，即分别对应一个最小值结点
     2. 任取两棵树的根结点，进⾏【合并】：⽐较其对应关键字的值，较⼤关键字的根结点成为双⽅孩⼦（⼦树）的⽗亲、成为另⼀个根的孩⼦
     3. 反复执⾏第2步操作直⾄合并完所有树，最终败者树的根揭示了当前记录中的最⼩值的编号
   • 使⽤⽅法：
     1. 取出根结点对应的最⼩值结点（叶结点），⽤下⼀个记录补上该结点（每个叶结点都对应一串候补结点序列）
     2. 摘出根结点和新结点所在的⼦树，对两个根结点进⾏【局部重建】：同建树时的【合并】操作
     3. 随后不断摘出与之相连的⼦树，继续对双⽅进⾏【局部重建】，反复操作直⾄重新建成败者树
        

        可事先在每⼀串候补结点序列尾追加⼀个值极⼤的结点，⽤于结点补空时填补位置（被挑出时即表明排序结束）

   • 算法优点：将直接⽐较所有关键字优化为局部重建时⽐较根结点对应关键字值，⼤幅减少了⽐较次数

外部排序性能分析：

• 时间复杂度：
  1. m个初始归并段的k路归并，归并趟数为\left \lceil \log_k m \right \rceil（同9.4“归并排序”），每一次归并都需进行\text{2}次I/O操作
  2. 置换-选择排序时所有记录都要进行\text{2}次I/O操作，选最值那⼀步的时间效率视实际所选算法⽽定
  3. 关于败者树：
     • k路归并败者树是一棵二叉树，高度h=\left \lceil \log_2 k \right \rceil+1（计算败者树高度时不包含最上层选出的根结点）
     • 利用败者树从k个记录中选出最值需比较h=\left \lceil \log_2 k \right \rceil次，即T_{查找}(n)=O(\log_2 k)
     • T_{建树}(n)=O(k \log_2 k)，⽤建树花费的相对较⼤时间换来⾼效的局部调整
• 空间复杂度：S(n)=O(1)

---

A 排序算法编程练习

A.1 插⼊类排序

【例1】写出链式存储结构（带头单链表）的直接插入排序算法

void insertSort(LinkList &L) {
    if (!L->next) return;   // 若表空则直接结束函数
    LNode *pre, *q, *p, *r; // pre、q：遍历有序部分寻找待插位置，p：指向待排结点，r：防p断链
    p = L->next->next;  // p从第二个数据结点开始作为待排结点（同直插）
    L->next->next = NULL;   // 断开链表，使L只有一个结点
    while (p) {
        pre = L;    // 初始化pre、q指向有序部分头部
        q = pre->next;
        while (q && q->data <= p->data) {   // 从头遍历，q指向第一个值大于p的结点（最终应插在pre、q之间）
            pre = q;
            q = q->next;
        }
        r = p->next;    // r防p断链
        p->next = q;    // 将p插入pre、q之间
        pre->next = p;
        p = r;
    }
}

【例2】有一个数组A存储着m + n个整型元素，元素下标从1开始存储，其前m个元素递增有序，后n个元素递增有序，设计算法使这个数组整体有序

void insertSort(int A[], int m, int n) {    /* 改写直接插排 */
    for (int i = m + 1; i <= m + n; i++) {  // 遍历后半段表的n个元素，往前直插即可
        if (A[i] < A[i - 1]) {
            A[0] = A[i];
            int j;
            for (j = i - 1; A[0] < A[j]; j--) {
                A[j + 1] = A[j];
            }
            A[j + 1] = A[0];
        }
    }
}

A.2 交换类排序

【例1】编写双向冒泡排序算法，在正反两个方向交替扫描（关键字为int型），即第一趟把最大关键字放序列最后，第二趟把最小关键字放序列最前，如此反复进行

void bubbleSort2Way(int A[], int n) {
    int low = 0, high = n - 1;  // 分别记录待排序元素的低地址和高地址
    bool flag = true;   // flag：记录冒泡过程中有无元素交换，无交换则退出循环
    while (low < high && flag) {    // 无序部分长度大于1，且上一轮进行了交换则循环
        flag = false;   // 置flag为false
        for (int i = low; i < high; i++)    // 从前往后冒泡，出现逆序则交换
            if (A[i] > A[i + 1]) {
                int temp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = temp;
                flag = true;
            }
        high--; // 多了1个有序最大值，上界缩1
        for (int i = high; i > low; i--)    // 从前往后冒泡，出现逆序则交换
            if (A[i] < A[i - 1]) {
                int temp = A[i];
                A[i] = A[i - 1];
                A[i - 1] = temp;
                flag = true;
            }
        low++;  // 多了1个有序最小值，下界升1
    }
}

【例2】有一个整型数组A存储了n个元素，元素序列无序，从下标1开始存储元素，设计算法让数组A的最后一个元素放在数组A整体排序后的最终位置上，结果返回其下标，要求关键字的比较次数不超过n

int partition(int A[], int n) { /* 改写快排的划分算法 */
    int low = 1, high = n;
    int pivot = A[high];    // 这里应将枢轴赋值为最后一个元素
    while (low < high) {    // 枢轴在右边，故从左边开始
        while (low < high && A[low] <= pivot) low++;    // 左小
        A[high] = A[low];
        while (low < high && A[high] >= pivot) high--;  // 右大
        A[low] = A[high];
    }
    A[low] = pivot; // 枢轴归位
    return low; // low即为所求的最终位置下标
}

【例3】设计算法在整型数组A[1...n]中找出第k小的元素（即从小到大排序后处于第k个位置上的元素）

int searchByOrder(int A[], int low, int high, int k) {  /* 改写快排的划分算法 */
    int pivot = A[low];
    int low0 = low, high0 = high;   // 记录初始时的高低索引
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;  // 右大
        A[low] = A[high];
        while (low < high && A[low] <= pivot) low++;    // 左小
        A[high] = A[low];
    }
    A[low] = pivot;
    if (low == k) return A[low];    // 若本趟排序枢轴最终位置即为k则直接返回枢轴
    if (k < low) return searchByOrder(A, low0, low - 1, k); // 左小：若k小则递归划分左边
    return searchByOrder(A, low + 1, high0, k); // 右大：若k大则递归划分右边
}

【例4】已知数组A[n]中所有元素均为不相同的正整数，设计算法把数组A中所有奇数移动到所有偶数前边的算法

void moveOdds(int A[], int n) { /* 改写快排的划分算法 */
    int low = 0, high = n - 1;
    while (low < high) {    // 每轮循环寻找一组奇偶数
        while (low < high && A[low] % 2 != 0) low++;    // 从左往右找偶数
        while (low < high && A[high] % 2 == 0) high--;  // 从右往左找偶数
        if (low < high) {   // 交换左边偶数与右边奇数
            int temp = A[low];
            A[low] = A[high];
            A[high] = temp;
            low++;  // 缩小索引范围
            high--;
        }
    }
}

【例5】顺序放置n个球，每个球的颜色是红、白、蓝之一，要求重新排列这些球，使得所有红色的球在前，白色的球居中，蓝色的球在后。假设放置球的序列在整型数组A中，0代表红球，1代表白球，2代表蓝球，设计算法为这些球排序

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void sortBalls(int A[], int n) {
    int low = 0, high = n - 1;  // low左边全是红色，high右边全是蓝色
    for (int i = 0; i <= high;) {   // 遍历数组
        if (A[i] == 0) {    // 若为红色，则与low位置交换
            swap(A[i], A[low]);
            low++;  // 更新low
            i++;    // i继续遍历
        } else if (A[i] == 1) { // 若为白色，则i继续遍历
            i++;
        } else {    // 若为蓝色，则与high位置交换
            swap(A[i], A[high]);
            high--; // 更新high，注意此时i不能继续遍历
        }
    }
}

A.3 选择类排序

【例1】请写出链式存储结构（带头单链表）的简单选择排序算法

void selectSort(LinkList &L) {
    LNode *pre, *p, *maxpre, *maxp; // 遍历指针及记录最大值结点的指针
    LNode *r = L;   // r：记录已排序的最后一个结点位置（初始无结点已排序）
    while (r->next) {
        pre = r->next;  // 重新初始化各指针
        maxpre = pre;   // p从待排序的第一个结点开始遍历
        maxp = pre;
        p = pre->next;
        while (p) {
            if (p->data > maxp->data) {
                maxpre = pre;
                maxp = p;
            }
            pre = p;
            p = p->next;
        }
        maxpre->next = maxp->next;  // 取下最大值结点maxp
        maxp->next = L->next;   // 将maxp头插L
        L->next = maxp;
        if (r == L) r = maxp;   // 若本次循环是第一次选择排序，则需更新r，更新为整个链表最大的结点
    }
}

【例2】有一种排序算法称为计数排序，其算法思想为选取一个待排元素，然后遍历整个数组，统计数组中有多少个元素比所选待排元素值小，假设统计出的计数值为cnt，则可根据计数值cnt在新的有序数组中找到待排元素的最终位置。现有一个数组A存放了n个互不相同的整型元素，请使用计数排序为数组A排序，结果存于数组B中

void countSort(int A[], int B[], int n) {
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (A[j] < A[i]) cnt++;
        }
        B[cnt] = A[i];
    }
}

【例3】有一个数组A存储了n个整型元素，元素从下标1开始存储，设计算法判断数组A是否构成了一个小根堆

bool isMinHeap(int A[], int n) {
    if (n % 2 == 0) {   // 若堆中有偶数个元素，则最后一个分枝结点只有左孩子
        if (A[n / 2] > A[n]) return false;  // 特判最后一个单分枝结点是否满足小根堆性质
        for (int i = n / 2 - 1; i >= 1; i--) {  // 判断其他双分枝结点是否满足小根堆性质
            if (A[i] > A[2 * i] || A[i] > A[2 * i + 1]) return false;
        }
    } else {    // 若堆中有偶数个元素，则所有分枝结点均有左右孩子
        for (int i = n / 2; i >= 1; i--) {  // 判断所有双分枝结点是否满足小根堆性质
            if (A[i] > A[2 * i] || A[i] > A[2 * i + 1]) return false;
        }
    }
    return true;    // 全部结点满足要求则说明是小根堆
}