内部排序

真题练习：可在站内题库按“排序算法”知识点筛选。

排序算法常通过选择题或算法设计题考查，需要能够辨别 不同排序算法的特征，并掌握 每种排序算法执行的具体流程。

排序概念

稳定性

排序算法的 稳定性 是指：在排序过程中，如果两个元素的键值相等，排序后它们的 相对顺序保持不变，那么这个排序算法就是 稳定的排序算法。

比如排序前的数组是这样：[... A ... B ...]，并且 A 和 B 的值相同。

如果排序后的数组是这样：[... B A ...]，那么排序算法就是不稳定的，反之排序算法就是 稳定的。

记忆提示

可以通过以下方式对排序算法的 稳定性 进行记忆：

常见的 $O(n\log n)$ 比较排序中，快速排序、堆排序通常不稳定，归并排序稳定。

常见的 $O(n^2)$ 排序中，冒泡排序、直接插入排序稳定，选择排序不稳定。

基数排序在每一趟都使用稳定排序时是稳定的；桶排序是否稳定取决于桶内排序和收集过程，不能只凭“分桶”就断定稳定。

元素移动次数

排序算法中的 元素移动次数，指的是在排序过程中对 数组元素进行位置变换的次数。

下表列出了各排序算法的 元素移动次数：

排序算法	元素移动次数	说明
冒泡排序	最坏 $O(n^2)$	每次交换涉及多次赋值，次数较多
选择排序	最多 $O(n)$ 次交换	每轮找到最小值后至多交换一次，移动少但比较多
插入排序	平均 $O(n^2)$	插入一个元素时可能连续后移一段元素
归并排序	$O(n\log n)$	每层归并都要在原数组与辅助数组之间复制
快速排序	平均 $O(n\log n)$，最坏 $O(n^2)$	每次划分区间时可能交换元素
堆排序	$O(n\log n)$	建堆和反复下坠会交换元素；具体移动次数受输入与实现影响
希尔排序	取决于增量序列	分组插入产生跨距移动，难用统一紧确式表示
桶排序	通常 $O(n)$ 次分配与收集	元素进入桶并按桶序收集，属于非比较排序
基数排序	$O(nd)$	$d$ 轮按位稳定分配与收集

选择排序至多进行 $O(n)$ 次交换，这是它“移动少”的常见优势；但它仍要进行 $O(n^2)$ 次比较。桶排序的数据移动、桶内比较和稳定性都取决于桶划分与桶内实现，不能与比较排序作不带条件的“最少”比较。

复杂度

排序方式	最好时间	平均时间	最坏时间	辅助空间	稳定性
冒泡排序	$O(n)$（有提前结束标记）	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
希尔排序	取决于增量序列	取决于增量序列	常见折半增量最坏 $O(n^2)$	$O(1)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	平均 $O(\log n)$，最坏 $O(n)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
桶排序	$O(n+k)$	数据分布均匀、桶内排序代价受控时为 $O(n+k)$	取决于分布与桶内算法	$O(n+k)$	取决于桶内排序与收集方式
基数排序	$O(d(n+k))$	$O(d(n+k))$	$O(d(n+k))$	$O(n+k)$	稳定

快速排序的递归栈

快速排序是原地排序算法，主要额外空间来自递归调用栈。划分均衡时递归树深度为 $\log_2 n$，每层局部变量只占 $O(1)$，所以平均辅助空间为 $O(\log n)$。例如，每次基准都恰好落在区间中部时就属于这种情况。若每次划分都极不均衡，递归深度会达到 $n$，最坏辅助空间为 $O(n)$。通过“先递归较短区间、较长区间改用循环”可把显式栈控制在 $O(\log n)$。

趟特征

在排序算法中，一趟（pass） 通常指 完成一次从头到尾（或部分范围）对数组进行处理的过程，这一过程中可能会比较、移动、插入或交换若干元素。 换句话说，一趟就是排序算法中最小的完整“循环工作单元”，通常对应于外层循环的一次执行。

不同的排序算法在每趟排序后，数组中的元素会呈现不同特征，总结为下表：

排序算法	一趟操作含义	一趟后的数组特征
冒泡排序	从头到尾依次比较相邻元素并交换	当前未排序区的最大元素被“冒”到末尾
选择排序	遍历剩余元素，找到最小值并放到当前位置	当前最小元素被放到未排序区起始位
插入排序	将下一个元素插入前面的已排序序列	前 $i$ 个元素有序
希尔排序	以某个 $gap$ 为间隔进行插入排序	每个间隔为 $gap$ 的子序列局部有序
归并排序	合并相邻的两个有序子数组	小规模有序区间合并为更大的有序区间
快速排序	选取基准并划分两侧区间	基准到达最终位置，左侧不大于它、右侧不小于它
堆排序	调整堆并把堆顶放到末尾	当前堆顶被移到最终位置，剩余区重新成堆
桶排序	元素被分配到不同桶	元素进入对应桶，但桶内未必已经有序
基数排序	按某一数位进行稳定排序	在保持已处理低位顺序的基础上，当前数位有序

伪代码

• 冒泡排序
• 插入排序
• 选择排序
• 基数排序
• 归并排序
• 希尔排序
• 快速排序
• 堆排序

BubbleSort(arr)
    n ← arr.length
    for i from 0 to n - 1
        for j from 0 to n - i - 2
            if arr[j] > arr[j + 1]
                swap arr[j], arr[j + 1]

InsertionSort(arr)
    n ← arr.length
    for i from 1 to n - 1
        key ← arr[i]
        j ← i - 1
        while j ≥ 0 and arr[j] > key
            arr[j + 1] ← arr[j]
            j ← j - 1
        arr[j + 1] ← key

SelectionSort(arr)
    n ← arr.length
    for i from 0 to n - 1
        minIndex ← i
        for j from i + 1 to n - 1
            if arr[j] < arr[minIndex]
                minIndex ← j
        swap arr[i], arr[minIndex]

RadixSort(arr)
    找到数组中最大值，确定最大位数 d
    for i from 1 to d
        对数组按第 i 位进行**稳定排序**

MergeSort(arr)
    if arr.length ≤ 1
        return arr
    mid ← arr.length / 2
    left ← MergeSort(arr[0 to mid - 1])
    right ← MergeSort(arr[mid to end])
    return Merge(left, right)

Merge(left, right)
    result ← []
    while left ≠ ∅ and right ≠ ∅
        if left[0] ≤ right[0]
            append left[0] to result
            remove left[0] from left
        else
            append right[0] to result
            remove right[0] from right
    append remaining elements of left and right to result
    return result

ShellSort(arr)
    n ← arr.length
    gap ← n / 2
    while gap > 0
        for i from gap to n - 1
            temp ← arr[i]
            j ← i
            while j ≥ gap and arr[j - gap] > temp
                arr[j] ← arr[j - gap]
                j ← j - gap
            arr[j] ← temp
        gap ← gap / 2

QuickSort(arr, low, high)
    if low < high
        pivotIndex ← Partition(arr, low, high)
        QuickSort(arr, low, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, high)

Partition(arr, low, high)
    pivot ← arr[high]
    i ← low - 1
    for j from low to high - 1
        if arr[j] ≤ pivot
            i ← i + 1
            swap arr[i], arr[j]
    swap arr[i + 1], arr[high]
    return i + 1

HeapSort(arr)
    BuildMaxHeap(arr)
    for i from arr.length - 1 down to 1
        swap arr[0], arr[i]
        MaxHeapify(arr, 0, i)

BuildMaxHeap(arr)
    n ← arr.length
    for i from n / 2 - 1 down to 0
        MaxHeapify(arr, i, n)

MaxHeapify(arr, i, n)
    largest ← i
    left ← 2 * i + 1
    right ← 2 * i + 2
    if left < n and arr[left] > arr[largest]
        largest ← left
    if right < n and arr[right] > arr[largest]
        largest ← right
    if largest ≠ i
        swap arr[i], arr[largest]
        MaxHeapify(arr, largest, n)

冒泡排序

冒泡排序（Bubble Sort）是一种 简单的排序算法，通过反复遍历数组，比较相邻元素并交换位置，将较大的（或较小的）元素逐步“冒泡”到数组的一端。过程如下：

1. 从数组开头开始，比较相邻的两个元素，如果顺序不对（例如前者大于后者，假设升序排序），则交换它们。
2. 遍历一遍后，最大（或最小）的元素会被“冒泡”到数组末尾（或开头）。
3. 对剩余的未排序部分重复上述步骤，每次遍历的范围减少一个元素，直到数组完全排序。

在升序排序中，较大的元素像气泡一样逐渐“浮”到数组末端（或较小的元素“沉”到开头），每次遍历都将一个元素推到正确位置，形似气泡在水中上升的过程，因此得名 “冒泡排序”。

比如，对于数组 5, 1, 4, 2, 8的前两次冒泡过程如下：

插入排序

插入排序（Insertion Sort）将数组分为 未排序部分 和 已排序部分，每次选取未排序部分的第一个元素作为插入元素，在已排序序列中 从后向前 扫描，找到相应位置并插入。

对于数组 4, 3, 2, 10, 12, 1, 5, 6 执行插入排序的过程：

插入排序可以分为 直接插入排序 和 折半插入排序，其不同点在于寻找插入位置时使用的是从后向前顺序查找还是折半查找。折半插入能减少关键字比较次数，但元素移动次数仍为 $O(n^2)$。

插入排序适合 大部分元素有序 的场景，因为这种情况下进行插入比较的次数较少，排序算法执行更加高效。

选择排序

在 选择排序（Selection Sort） 中，数组被分为 有序子数组 和 无序子数组 这两个部分。 每次迭代时，算法会 在未排序部分中找到最小元素，将其放到已排序部分的末尾（与有序子数组的下一个元素交换位置）。这样，每一次选择操作后，未排序部分减少一个元素，而有序部分则增加一个元素。

以排序数组 11, 25, 12, 22, 64 为例：

有序子数组	无序子数组	无序区最小值
()	(11, 25, 12, 22, 64)	11
(11)	(25, 12, 22, 64)	12
(11, 12)	(25, 22, 64)	22
(11, 12, 22)	(25, 64)	25
(11, 12, 22, 25)	(64)	64
(11, 12, 22, 25, 64)	()	—

归并排序

归并排序（Merge Sort）是一个典型的 分而治之 策略的应用。它将一个大问题分解成若干小问题分别解决，然后将这些小问题的解合并为大问题的解。归并排序的主要思想是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

基本思想：

1. 分解：分解待排序的数据数组为两个长度相等（或几乎相等）的子数组。
2. 递归：递归地排序两个子数组。
3. 合并：合并（归并）两个已排序的子数组以产生排序好的数据数组。

快速排序

快速排序（Quick Sort）的核心思想和归并排序一样，也是 分而治之，其步骤如下：

1. 选择一个基准元素（Pivot）：从数组中选择一个元素作为基准。
2. 分区（Partition）：重新排列数组，使得所有小于基准的元素都在其左侧，所有大于基准的元素都在其右侧。在这个分区结束之后，该基准就处于数组的最终排序位置。
3. 递归地排序子序列：递归地对基准左侧和右侧的子数组进行快速排序。

代码实现

快排代码包含两个函数，一个是 partition，用于选择基准元素，并对其进行分区。

其中分区的实现方式有很多种，此处使用双指针法实现分区，该算法比较简短，方便记忆。

// [low, high] 为分区范围，返回分区后 pivot 在数组中的下标
int partition(int a[], int low, int high) {
    int pivot = a[low];     // 设置基准元素为 [low, high] 区间中的第一个元素
    int l = low, r = high;  // 设置双指针
    while (l < r) {
        while (l < r && a[r] >= pivot) r--; // 从右到左寻找小于 pivot 的元素
        while (l < r && a[l] <= pivot) l++; // 从左到右寻找大于 pivot 的元素
        if (l < r) swap(a[l], a[r]);        // 交换两个元素
    }
    swap(a[low], a[r]); // 将 pivot 置换到中间位置
    return r;
}

void quickSort(int a[], int low, int high) {
    // 递归的结束条件，不要遗漏
    if (low < high) {
        int pivotIdx = partition(a, low, high);
        // 递归地处理基准左右两个区间
        quickSort(a, low, pivotIdx - 1);
        quickSort(a, pivotIdx + 1, high);
    }
}

快速排序的代码实现需要熟练掌握（能够手写代码），在数据结构的算法解答题中可以作为兜底的方案。

单向递归算法

每一次基于基准元素执行分区操作后，可以基于基准元素的位置将数组分为两个部分，这个时候 基准元素的位置与最后有序数组中的位置相同。

基于这一点可以解决顺序统计问题。下面的分区按升序排列，因此代码中的 $k$ 表示 排序后下标为 $k$ 的元素，也就是从 0 开始计数的第 $k+1$ 小元素。若要寻找长度为 $n$ 的数组中从 1 开始计数的 第 $k$ 大元素，应把目标下标换算为 $n-k$。

// 分区算法实现与标准快排相同，这里不赘述
int partition(int a[], int low, int high) { ... }

// 寻找升序后下标为 k 的元素（0 <= k < n）
int quickSelect(int a[], int low, int high, int k) {
    if (low == high) {
        return a[low];
    }

    int pivotIdx = partition(a, low, high);
    if (pivotIdx == k) {
        return a[pivotIdx];
    }
    if (pivotIdx < k) {
        return quickSelect(a, pivotIdx + 1, high, k);
    }
    return quickSelect(a, low, pivotIdx - 1, k);
}

堆排序

堆排序的核心在于利用 堆的性质 进行排序，在了解堆排序过程之前，需要了解堆的基本概念。

堆

在二叉树一节中我们提到，二叉树的存储方式 包含 链接存储 和 顺序存储 两种。 堆就是采用 顺序存储 的方式，在这种方式中，我们使用一个数组来模拟一颗二叉树，二叉树中的结点操作被转化为数组元素操作。

满足以下性质的树 被称为 堆（Heap）：

1. 结构性质：堆总是一颗 完全二叉树，即除了最后一层之外的其他每一层都被元素填满，且最后一层的元素都尽可能地靠左排列。
2. 有序性质：树中的每个结点 相对于 子结点 都保证有序关系，要么父结点的值都 大于等于 子结点的值，要么都 小于等于 子结点的值，按照这种有序关系堆可以分为两种类型：
   • 大根堆（Max Heap）：堆中的任意结点，其值都 ≥ 其子结点的值。这意味着 根结点是最大值。
   • 小根堆（Min Heap）：堆中的任意结点，其值都 ≤ 其子结点的值。这意味着 根结点是最小值。

基于这些性质，堆常被用于实现 优先队列。对于大根堆，我们总能在 $O(1)$ 时间内读取最大元素（根结点）；对于小根堆，也能在 $O(1)$ 时间内读取最小元素。插入和删除堆顶通常需要 $O(\log n)$ 时间重新调整。

实现

堆通常使用数组来实现，而不需要使用真正的树或链表结构。利用数组实现堆时，每个元素都有一个固定的位置，而该位置与元素在树中的位置有关。

假设数组的起始索引为 1，若某元素的索引为 i，则它的：

• 左孩子的索引为 $2i$；
• 右孩子的索引为 $2i+1$；
• 父结点的索引为 $\lfloor i/2\rfloor$。

如果数组的起始索引为 0，若某元素的索引为 i，则它的：

• 左孩子的索引为 $2i+1$；
• 右孩子的索引为 $2i+2$；
• 父结点的索引为 $\lfloor(i-1)/2\rfloor$。

操作

对于堆，重点掌握 堆化（heapify）、构建初始堆、删除 和 插入 操作。

堆化

堆化是从某个结点开始，调整以该结点为根的子树，使其满足堆性质（以最大堆为例说明其过程）：

• 比较 当前结点 与 左右子结点 的值。
• 如果某个子结点 比当前结点大，交换当前结点与较大的子结点。
• 交换后，继续对 被交换的子结点 递归地执行堆化，直到子树满足堆性质。

以大根堆 50,13,40,30,20,22,24,15,11 为例，若我们从结点 13 执行堆化，会发生如下图所示的过程：

注意堆化的过程是递归的，当我们交换父结点和子结点后，需要从子结点进一步执行堆化操作。

构造初始堆

构造初始堆有两种方式：

• 方法 1：向一个初始为空的堆中不断 插入 新的元素。
• 方法 2：将无序数组转化为最大堆，核心是从 最后一个非叶子结点 开始，从后向前逐一对每个子树执行 堆化 操作。

以数组 1,3,5,4,6,13,10,9,8,15,17 为例，假设我们使用方法 2 将其初始化为大根堆，会发生如下图所示的过程：

删除

堆中的删除一般都发生在 堆顶，其过程如下：

• 将堆顶元素和堆中最后一个元素互换，然后删除最后一个结点
• 对新的堆顶执行 堆化，调整堆使其重新满足最大堆性质

插入

在堆中插入新元素后，需维护堆性质。

• 将新元素添加到堆底（数组末尾）。

• 从新元素开始，向上与父结点比较，若 大于父结点 则交换（上浮）。

• 重复上浮直到满足堆性质或到达堆顶。

• 堆化

• 构造初始堆

• 堆插入元素

• 堆删除元素

// 调整 i 结点为根的子树，使其满足堆的性质
void heapify(int heap[], int size, int i) {
    int largest = i;       // 假设当前结点是最大的
    int left = 2 * i + 1;  // 左结点下标
    int right = 2 * i + 2; // 右结点下标
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }
    // 如果最大值不是根结点
    if (largest != i) {
        swap(heap[i], heap[largest]);
        heapify(heap, size, largest);  // 递归堆化受影响的子树
    }
}

// 建立最大堆
void buildHeap(int heap[], int size) {
    // 从最后一个非叶结点开始，向前堆化每个结点
    for (int i = (size / 2) - 1; i >= 0; i--) {
        heapify(heap, size, i);
    }
}

// 向大小为 size 的堆中插入元素 value
void heapInsert(int heap[], int *size, int value) {
    heap[*size] = value;
    int current = *size;
    int parent = (current - 1) / 2;

    // 如果新插入的元素比父结点的元素大，需要将其向上移动
    while (current > 0 && heap[current] > heap[parent]) {
        swap(heap[current], heap[parent]); // 交换当前结点和父结点
        current = parent;
        parent = (current - 1) / 2; // 重新计算当前结点和其父结点的位置
    }

    (*size)++;  // 增加堆的大小
}

// 删除堆根结点
void heapDelete(int heap[], int *size) {
    if (*size <= 0) {
        return;
    }
    heap[0] = heap[*size - 1]; // 将堆顶元素替换为最后一个元素
    (*size)--;   // 将堆大小减 1
    heapify(heap, *size, 0);   // 调整堆
}

过程

堆排序（Heap Sort）其主要思想是将待排序的序列构造成一个 大顶堆 或 小顶堆，然后交换堆顶和最后一个元素的位置，使最大或最小的元素放到序列的末尾。这样，就得到一个部分有序的序列。接下来，再对剩下的部分重新调整为大顶堆或小顶堆，并重复上述过程，直到整个序列有序。

堆排序的主要步骤：

1. 构造初始堆：将给定无序序列构造成一个大顶堆（对于升序排序）或小顶堆（对于降序排序）。
2. 交换数据：将堆顶元素与末尾元素交换，这样最大元素就位于序列的末尾。然后，将未排序的序列的长度减 1，因为最后一个元素已经排序好了。
3. 重建堆：对于剩下的未排序的序列，重新调整为大顶堆。
4. 重复步骤 2 和 3，直到整个序列有序。

下面按代码采用的 0 下标数组 说明调整堆过程：

1. 选择一个结点 $i$，它的左子结点为 $2i+1$，右子结点为 $2i+2$。
2. 如果结点 i 的值小于其子结点的值，则找到 最大的子结点。
3. 将结点 i 与 最大的子结点 交换。
4. 交换后可能会破坏下一层的堆结构，所以需要对换到的子结点重复步骤 1‑3 的调整，直到整个子树满足堆的性质。

堆排序的代码实现如下所示：

void heapSort(int heap[], int size) {
    // 构建最大堆 buildHeap
    for (int i = (size / 2) - 1; i >= 0; i--) {
        heapify(heap, size, i);
    }

    // 一个个从堆中取出元素
    for (int i = size - 1; i >= 0; i--) {
        swap(heap[0], heap[i]); // 将当前最大元素（堆顶）移到数组末尾
        heapify(heap, i, 0);    // 调整堆以维护最大堆性质
    }
}

希尔排序

希尔排序（Shell Sort）是一种 基于插入排序 的改进算法，通过分组和逐步减小步长来提高效率。

希尔排序的过程如下所示：

1. 确定初始步长（增量）：
   • 选择一个初始步长（gap），通常可以 取数组长度的一半（例如 gap = n/2）。
2. 分组插入排序：
   • 将数组按步长 gap 分成若干组，每组内的元素相距 gap 个位置。
   • 对每组进行插入排序。例如，若 gap=4，比较和排序索引为 0,4,8... 的元素，1,5,9... 的元素，依此类推。
3. 减小步长：
   • 将步长缩小（通常除以 2 或按增量序列递减），例如 gap = gap/2。
   • 重复步骤 2，对新的分组进行插入排序。
4. 重复直到步长为 1：
   • 当步长减小到 1 时，相当于对整个数组进行一次标准插入排序。此时数组已接近有序，插入排序的效率较高。
5. 排序完成：
   • 步长为 1 的插入排序完成后，数组完全有序。

注意

虽然希尔最初提出时建议初始 gap（增量序列）为 n/2 并逐步折半，但在实践中 gap 的选取是灵活的，并不强制要求必须为数组长度的一半。

以数组 32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68 为例进行 希尔排序，数组长度为 14，初始步长为 7，然后选择步长 3、1，依次按照步长对所有子数组排序。

桶排序

桶排序（bucket sort）核心思想是将数据映射到不同的 桶 中，然后对每个桶内部排序，最后按桶序合并。它适合键值范围已知且数据分布较均匀的情形：若大量元素集中到同一个桶，性能会退化到桶内排序算法的复杂度。

桶排序的步骤如下：

1. 选择合适 桶数，并将数据放入桶中
2. 桶内数据排序
3. 合并 所有桶

举个例子，对 12, 9, 24, 4, 19, 21, 14, 6, 2, 16 进行桶排序的过程如下：

基数排序

基数排序（Radix Sort）的核心思想是将整数分解为单独的数字，然后进行多轮排序，最终使数据有序。

基数排序分为 低位优先（LSD，Least Significant Digit first）和 高位优先（MSD，Most Significant Digit first）两种方案。这里重点掌握 LSD 的方案，MSD 的方式了解即可。

低位优先

1. 先按照最低位进行一次稳定排序（常用计数排序或按位分配/收集）。
2. 然后按照次低位进行稳定排序，并保持上一轮的相对顺序。
3. 依次进行，直到最高位排序完成。

以上排序的效果如下：

首先对最低位排序，然后对次低位排序，最后对最高位排序。通过三轮排序，可以保证结果序列是有序的。

高位优先

MSD（高位优先）基数排序的核心思想是从最高位开始，对数据进行递归分类，直到所有数字或字符串都排好序。

如上图所示，MSD 首先根据最高位对数据进行分组，然后再根据次高位对数据进行分组，以此类推，递归直到每组中只有一个元素。

MSD 基数排序适用于 字符串或变长数据，因为它先处理最高位，可以提前分组。适合 字典序排序，如 IP 地址、文件名、长整型数值等。

对比

方式	低位优先（LSD）	高位优先（MSD）
排序顺序	从低位到高位	从高位到低位
是否递归	通常否	通常是
适用数据	等长数据（整数、固定长度字符串）	变长数据（字符串、IP 地址）
适用场景	大量数值排序	变长字符串、字典序排序
实现难度	较简单	需要递归，较复杂

手算排序的判别、证明与选型

比较排序为什么绕不开 $n\log n$

对于 $n$ 个互不相同的记录，任何只通过“两元素比较结果”作决定的排序算法，都至少要区分 $n!$ 种可能的初始排列。把比较过程看成二叉判定树，若高度为 $h$，最多只有 $2^h$ 个叶子，因此必须满足

这解释了为什么归并、快速和堆排序的比较次数可以达到 $O(n\log n)$，却不能对任意关键字再普遍降低一个数量级。计数、桶和基数排序不违背这个下界，因为它们额外使用了“关键字范围有限、可按位或按桶映射”的信息；若关键字范围 $k$ 极大、数据分布极端或记录不能拆位，这些非比较排序的空间与桶内代价就必须重新计算。

逆序对把“近乎有序”量化

若一对下标 $i<j$ 却有 $a_i>a_j$，称它们构成一个逆序对，记总数为 $I$。直接插入排序中，一个元素左移跨过一个较大元素，恰好消去一个逆序对，所以元素后移总次数正好为 $I$，比较次数至多为 $I+n-1$。带提前结束标记的冒泡排序中，每次相邻交换也恰好消去一个逆序对，交换次数同样为 $I$。

因此，当 $I$ 很小，直接插入排序比其最坏的 $O(n^2)$ 表现好得多；当 $I=\Theta(n^2)$ 时，它又会回到二次代价。这里的结论针对“直接插入”和相邻交换的冒泡，不可套到选择排序：选择排序每趟仍要扫描无序区寻找最小值，即使数组已经有序，比较次数也仍是 $\Theta(n^2)$。

稳定性由具体操作决定

稳定的含义是相同关键字携带的附加信息仍保持原次序。例如记录 $2_A,2_B,1$ 用选择排序时，第一趟把 $1$ 与 $2_A$ 交换，得到 $1,2_B,2_A$，于是相同键的相对次序已经被破坏。归并排序则应在两段当前元素相等时优先取左段元素，也就是合并判断写成“左值 $\le$ 右值”；若改成严格小于后优先取右段，归并也会变得不稳定。

算法名称本身不是稳定性的充分理由。快速排序的分区交换、堆排序的堆顶与末尾交换一般会跨越相同键；基数排序只有每一趟所用的分配—收集过程稳定时，低位形成的相对次序才会被高位保留。遇到“某实现是否稳定”的题，应直接检查相等记录有没有可能跨越彼此。

根据约束选择算法

题目给出的约束	优先考虑	还要核对的条件
数据量小或基本有序	直接插入排序	逆序对少才有优势
要求稳定且时间界稳定	归并排序	需要 $O(n)$ 辅助空间
只能使用常数级辅助空间，且最坏也要 $O(n\log n)$	堆排序	一般不稳定，建堆不是把数组完全排序
平均性能优先、可接受递归栈	快速排序	基准不均衡会退化，需有终止条件
关键字为固定长度整数或字符	基数排序	每趟必须稳定，桶数与位数要受控
值域已知且分布较均匀	桶排序	桶内排序与偏斜分布决定实际复杂度

手算一趟时还要分清“不变量”与“全局有序”。快速排序的一次划分后，基准元素已在最终位置，但左右子区仍未分别有序；堆排序每轮把当前最大值放到末尾，末尾有序区扩大而前部只保证是堆；自底向上的归并排序在第 $t$ 趟后只保证长度至多 $2^t$ 的相邻段各自有序。用这些不变量反推算法，比只记住图形外观更可靠。

精确计数题的常用切入点

选择排序无论初始序列如何，第一趟比较 $n-1$ 次、第二趟比较 $n-2$ 次，合计为

它至多交换 $n-1$ 次，但“交换少”不等于“比较少”。直接插入排序和冒泡排序则会随逆序对数量变化；题目若给出具体数组，应优先数逆序对或逐趟记录，而不是只写最坏复杂度。

快速排序的关键是分区而非递归名称。一次分区完成后，基准已到最终下标，所有左侧键不大于它、右侧键不小于它；因此查找第 $k$ 小元素只需递归进入包含第 $k$ 个下标的一边，平均时间为 $O(n)$，但最坏仍可能为 $O(n^2)$。递归排序两边与只追踪一边的选择问题，终止条件和复杂度不能混为一谈。

自底向上建堆是 $O(n)$ 而非 $O(n\log n)$：大多数结点靠近叶子，调整距离很短；只有少量靠近根的结点可能下沉很多层。把每个结点都粗略乘一个 $\log n$ 只会得到不紧的上界。堆排序随后有 $n-1$ 次“交换堆顶、缩小堆、下滤”，这部分才合计为 $O(n\log n)$。