数据结构-08：内排序

直接插入排序

插入排序维护一个“已经排好序的前缀区间”，每次从未排序部分拿出第一个元素，把它插入到前缀中的正确位置。它的优势不是渐进复杂度，而是实现简单、常数小、对几乎有序的数据非常快，因此常被用在小数组排序或高级排序算法的局部优化中。

代码实现

template <class KEY, class OTHER>
void simpleInsertSort(SET<KEY, OTHER> a[], int size) {
    int k;
    SET<KEY, OTHER> tmp;
    for (int j = 1; j < size; ++j) {
        tmp = a[j]; // 保存待插入元素
        for (k = j - 1; k >= 0 && tmp.key < a[k].key; --k) {
            a[k + 1] = a[k]; // 已排序区间中较大的元素后移
        }
        a[k + 1] = tmp; // 插入到最终位置
    }
}

直接插入排序的循环不变量是：进入第 j 轮时，区间 a[0..j-1] 已经有序。代码先把 a[j] 暂存到 tmp，再把已排序区间中所有比 tmp 大的元素向后移动一格，最后把 tmp 放进空出来的位置。它像整理扑克牌：手里的牌始终有序，新牌插入到正确位置。

效率分析

最好情况： $O(n)$ ，当数据已经有序时。
最坏情况： $O(n^2)$ ，当数据完全逆序时。
平均情况： $O(n^2)$ ，稳定的排序算法，因为每次插入都需要遍历已排序部分。
使用情况：排序元素较少，且几乎是已排序。

稳定性的原因在于：寻找插入位置时通常只移动“严格大于”待插入元素的项，遇到相等关键字不会越过它们，所以相等元素的相对顺序保持不变。

折半插入排序

利用折半查找法快速找到插入位置，减少比较次数。
最坏情况下总的移动次数还是 $O(n^2)$ ，但比较次数减少到 $O(n\log n)$ 。

折半插入排序只优化“找位置”的比较次数，并不能减少“挪元素”的次数。数组中间插入元素仍然要整体后移，因此总时间复杂度仍由移动成本主导。

希尔排序

设有 n 个对象待排序；
首先取一个 gap < n 作为增量；
将待排序的 n 个对象分成 gap 个子序列，每个子序列包含相隔 gap 个元素的对象；
在每个子序列中进行直接插入排序；
缩小增量 gap，重复上述过程，直到 gap 为 1。

希尔排序可以看作“带间隔的插入排序”。当 gap 较大时，元素可以一次跨过很远的位置，快速消除严重逆序；当 gap 最终变为 1 时，算法退化为普通插入排序，但此时序列通常已经接近有序，所以最后一轮成本会明显下降。它不稳定的原因是相同关键字可能在不同 gap 子序列中被跨距离移动，破坏原来的相对顺序。

代码实现

template <class KEY, class OTHER>
void shellSort(SET<KEY, OTHER> a[], int size) {
    int step, i, j;
    SET<KEY, OTHER> tmp;
    for (step = size / 2; step > 0; step /= 2) {
        for (i = step; i < size; ++i) {
            tmp = a[i]; // 保存当前待插入元素
            for (j = i - step; j >= 0 && a[j].key > tmp.key; j -= step) {
                a[j + step] = a[j]; // 按gap间隔后移
            }
            a[j + step] = tmp; // 插入到当前gap子序列中的正确位置
        }
    }
}

效率分析

不同的增量序列有不同的时间性能；
希尔建议 gap 从 N/2 开始，逐渐平分减小到 1；
最坏时间复杂度为 $O(n^2)$ ，但平均时间复杂度通常可粗略记为 $O(n^{3/2})$ ，不稳定的排序算法。

希尔排序的复杂度很难像插入排序那样用一个简单式子完全概括，因为它高度依赖 gap 序列。复习时可以先记住两个事实：最后一趟一定是普通插入排序；前面的较大 gap 会让序列提前接近有序，从而降低最后一趟的移动成本。

选择排序

首先，从待排序的 n 个元素中选出最小的元素，存放在序列的起始位置；
然后，再从剩余的 n-1 个元素中选出最小的元素，放在已排序序列的末尾；
最后，重复上述过程，将每次得到的元素排成一个序列直到所有元素均排序完成。

选择排序的循环不变量是：第 $i$ 趟结束后，前 $i$ 个位置已经放入全局最小的 $i$ 个元素。它的比较次数几乎不受输入有序程度影响，因为每一趟都必须扫描完整的未排序区间来找到最小值。

直接选择排序

首先在所有元素中逐个比较选出最小元素；
然后将最小元素与第一个元素交换位置；
接着在剩余的 n-1 个元素中重复上述过程，直到所有元素均排序完成。
时间复杂度为 $O(n^2)$ ，不稳定的排序算法。

直接选择排序不稳定的关键在“交换”。如果最小元素从后面被换到前面，它可能越过若干个与当前元素关键字相等的元素，从而改变相等元素的原始相对次序。

代码实现

template <class KEY, class OTHER>
void simpleSelectSort(SET<KEY, OTHER> a[], int size) {
    int i, j, min;
    SET<KEY, OTHER> tmp;
    for (i = 0; i < size - 1; i++) {
        min = i;
        for (j = i + 1; j < size; j++) {
            if (a[j].key < a[min].key) min = j; // 记录未排序区间最小元素下标
        }
        tmp = a[i]; // 将最小元素交换到已排序区间末尾
        a[i] = a[min];
        a[min] = tmp;
    }
}

直接选择排序的循环不变量是：第 i 轮开始时，a[0..i-1] 已经放好了全局最小的 i 个元素。第 i 轮只负责在剩余区间 a[i..size-1] 中找最小值，并把它交换到 a[i]。它的比较次数几乎不受初始有序程度影响，因此即使原数组已经有序，也仍然会扫描剩余区间。

堆选择排序

使用 buildHeap 对 $N$ 个元素创建一个堆；
如果使用优先级队列，可以通过调用 $N$ 次 deQueue 取出每一个项完成排序。
原地堆排序通常使用大顶堆：每次把堆顶最大元素交换到数组末尾，再对剩余前缀向下过滤。
建堆的复杂度为 $O(n)$ ，每次调整堆需要 $O(\log n)$ 的时间。
总时间复杂度为 $O(n\log n)$ ，不稳定的排序算法。

代码实现

template <class KEY, class OTHER>
void heapSelectSort(SET<KEY, OTHER> a[], int size) {
   int i;
   SET<KEY, OTHER> tmp;
   // 创建初始大顶堆，下面代码按0下标存储
   for (i = size / 2; i >= 0; --i) {
       percolateDown(a, i, size);
   }
   // 执行N - 1次“删除堆顶”操作
   for (i = size - 1; i > 0; --i) {
       tmp = a[0]; // 取出堆顶最大元素
       a[0] = a[i]; // 将最后一个元素放到堆顶
       a[i] = tmp; // 将最大元素放到已排序部分
       percolateDown(a, 0, i); // 只调整未排序的前i个元素
   }
}

percolateDown 函数的实现参考优先级队列

堆排序的读法与优先级队列相同：前半段先把数组前缀整理成大顶堆，后半段反复把堆顶最大值交换到数组末尾。每完成一轮，数组右侧的已排序区间就扩大一格，而左侧仍保持堆结构。由于交换可能跨越很远的位置，相等元素的相对顺序可能改变，所以堆排序不稳定。

交换排序

交换排序即根据对数据元素的比较确定是否交换二者的位置。
常见的交换排序有冒泡排序、快速排序等。

交换排序的共同点是通过比较元素对并交换位置来减少逆序。冒泡排序每次只交换相邻元素，所以过程稳定但移动距离短；快速排序通过一次划分让元素跨较远距离移动，平均效率高，但稳定性通常无法保证。

冒泡排序

从头到尾比较相邻元素，将小的换到前面，大的换到后面，完成一趟过程称为一次起泡，可以将最大元素交换到最后位置。
在从头到倒数第二个元素完成第二次起泡，以此类推，经过 n - 1 次起泡后将倒数第 n - 1 个大的元素放到第二个单元。

代码实现

template <class KEY, class OTHER>
void bubbleSort(SET<KEY, OTHER> a[], int size) {
    int i, j;
    SET<KEY, OTHER> tmp;
    bool flag = true; // 标志是否有交换发生
    for (i = 1; i < size && flag; ++i) {
        flag = false; // 本趟开始时先假设没有交换
        for (j = 0; j < size - i; ++j) {
            if (a[j].key > a[j + 1].key) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                flag = true; // 发生交换，说明可能仍未有序
            }
        }
    }
}

冒泡排序的循环不变量是：完成第 i 趟后，数组最后 i 个位置已经放好了最大的 i 个元素。内部循环只比较相邻元素，所以如果本趟没有发生任何交换，说明所有相邻元素都已经满足顺序，整个数组已经有序，可以提前结束。

性能分析

对于未优化的冒泡排序（没有 flag 记录是否交换），平均时间复杂度为 $O(n^2)$ ，稳定的排序算法。
对于优化过的冒泡排序（有 flag 记录是否交换），平均时间复杂度仍然为 $O(n^2)$ ；由于只在严格大于时交换，相等元素相对顺序不变，因此仍然是稳定的排序算法。

flag 优化改变的是最好情况：若数组本来有序，第一趟没有任何交换，算法可以立即结束，时间复杂度降为 $O(n)$ 。但对于随机数据，仍然通常需要多趟相邻比较。

快速排序

思路：任选一个（此处选择首个）关键字作为界点，将序列划分成两部分，使得左边部分的所有关键字都小于或等于界点，右边部分的所有关键字都大于或等于界点。
然后对两边分别进行递归快速排序。

快速排序的核心是 partition：一趟划分后，枢轴元素已经处在它最终应该在的位置，左侧元素不大于它，右侧元素不小于它。之后左右两边互不影响，可以递归处理。它平均很快，是因为每次若能把问题大致分成两半，就会得到类似归并排序的 $O(n\log n)$ 递归层数；最坏情况出现在每次划分都极不均衡时。

代码实现

template <class KEY, class OTHER>
void quickSort(SET<KEY, OTHER> a[], int low, int high) {
    int mid;
    if (low >= high) return; // 递归终止条件
    mid = divide(a, low, high); // 分割操作
    quickSort(a, low, mid - 1); // 对左半部分递归排序
    quickSort(a, mid + 1, high); // 对右半部分递归排序
}

// 一趟划分的实现
template <class KEY, class OTHER>
int divide(SET<KEY, OTHER> a[], int low, int high) {
    SET<KEY, OTHER> k = a[low]; // 选择基准元素
    do {
        while (low < high && a[high].key >= k.key) --high; // 从右向左找第一个小于k的元素
        if (low < high) a[low++] = a[high]; // 将找到的元素放到左边
        while (low < high && a[low].key <= k.key) ++low; // 从左向右找第一个大于k的元素
        if (low < high) a[high--] = a[low]; // 将找到的元素放到右边
    } while (low != high);
    a[low] = k; // 将基准元素放到正确位置
    return low; // 返回基准元素的位置
}

快速排序中最关键的是 divide：它不是完整排序，而是把基准元素 k 放到最终位置，并保证左侧元素不大于它、右侧元素不小于它。此后基准元素再也不需要移动，递归只处理左右两个子区间。第一次看这段代码时，可以把 low 和 high 想成两个从两端向中间靠拢的“空位搬运指针”：右边找到小元素填左空位，左边找到大元素填右空位，直到两个指针相遇。

性能分析

最坏情况：每次枢纽元素都为最大或最小，时间复杂度为 $O(n^2)$ 。

$\begin{aligned} T(N) &= T(N - 1) + cN \\ &= T(1) + c(2 + 3 + \cdots + N) \\ &= O(N^2) \end{aligned}$

改进方法：随机选取界点，或者最左，最右，中间三个元素的中位数作为界点，通常可以避免最坏情况。

最好情况：每次枢纽元素都能将序列分成两半，时间复杂度为 $O(n\log n)$ 。

$\begin{aligned} T(N) &= 2T(N / 2) + cN \\ &= cN\log_2 N + N \\ &= O(N\log N) \end{aligned}$

平均情况：每一个元素都可以当作界点，共 $n$ 种情况，平均时间复杂度为 $O(n\log n)$ ，不稳定的算法。

$T(N)=\frac{2}{N}\sum_{i=0}^{N-1}T(i)+cN=O(N\log N)$

空间复杂度： $O(\log n)$ ，来自平均情况下的递归调用栈深度。

归并排序

思路：将待排序的序列分成两半，分别对两半进行归并排序，然后将两半有序的序列合并成一个有序序列。
性能：
最坏时间复杂度： $O(n\log n)$
平均时间复杂度： $O(n\log n)$
辅助空间： $O(n)$ ，需要额外的空间来存储合并后的结果。
稳定的排序算法。

归并排序的优势是复杂度稳定，不依赖输入初始顺序；缺点是需要额外数组进行合并。它特别适合链表排序和外排序，因为合并两个有序序列可以顺序扫描完成，对随机访问的依赖较低。

递归实现

// 合并两个有序表
template <class KEY, class OTHER>
void merge(SET<KEY, OTHER> a[], int left, int mid, int right) {
    SET<KEY, OTHER> *temp = new SET<KEY, OTHER>[right - left + 1];
    int i = left, j = mid, k = 0; // mid表示右半区的起始位置

    while (i < mid && j <= right) {
        if (a[i].key <= a[j].key) { // 相等时先取左侧，保持稳定性
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }

    while (i < mid) {
        temp[k++] = a[i++];
    }
    while (j <= right) {
        temp[k++] = a[j++];
    }

    for (i = 0, k = left; k <= right;) {
        a[k++] = temp[i++];
    }
    delete[] temp; // 释放临时数组
}

// 归并实现
template <class KEY, class OTHER>
void mergeSort(SET<KEY, OTHER> a[], int left, int right) {
    if (left >= right) return; // 递归终止条件
    int mid = (left + right) / 2;
    mergeSort(a, left, mid); // 对左半部分进行归并排序
    mergeSort(a, mid + 1, right); // 对右半部分进行归并排序
    merge(a, left, mid + 1, right); // 合并两部分
}

归并排序的核心不变量是：调用 merge(a, left, mid, right) 时，左半区间 a[left..mid-1] 和右半区间 a[mid..right] 已经各自有序。merge 做的只是把两个有序序列线性合并成一个更大的有序序列。递归版的 mergeSort 先不断拆分到单个元素，再在回溯过程中逐层合并。

非递归实现（仅供参考）

template <class KEY, class OTHER>
void mergeSortNonRecursive(SET<KEY, OTHER> a[], int n) {
    // 待排序数组a中a[0]不使用，待排序下标为1到n
    int low = 1; // 被合并的两个表中第一个表的首地址
    int up; // 被合并的两个表中第二个表的末地址
    int m = 1; // 被合并的两个表中第一个表的长度，初始时为1
    SET<KEY, OTHER>* aa;
    aa = new SET<KEY, OTHER>[n + 1]; // 用于合并的辅助数组，aa[0]不使用
    while (m < n) {
        up = min(low + 2 * m - 1, n);
        Merge(a, aa, n, low, up, m); // a[low]至a[low + m - 1],a[low + m]至a[up]进行合并
        if (up + m < n) low = up + 1; // up + m >= n说明被合并的另一张表不存在
        else {
            m *= 2;
            low = 1;
        }
    }
    delete[] aa; // 释放辅助数组
}

基数排序（口袋排序法）

通过分配的方法对整数进行排序。
以排序十进制数为例：
首先将元素按个位数分别放入十个口袋，然后将每个口袋中的元素倒出来；
接着将元素按十位数分别放入十个口袋，然后将每个口袋中的元素倒出来；
再按百位数分配；
到最后一次倒出来时，所有元素就已经排好序了。

基数排序依赖“稳定分配”。按个位分桶后收回，不能打乱同一桶内元素的原始顺序；再按十位、百位继续分桶时，低位已经形成的顺序才能被保留下来。代码中每个桶维护头指针 bucket[k] 和尾指针 last[k]，新元素总是追加到桶尾，正是为了保持稳定性。

代码实现

// 待排序的元素组成一个不带头结点的单链表；
// 每个口袋也用一个不带头结点的单链表来存储。

template <class OTHER>
struct Node {
    SET<int, OTHER> data;
    Node* next;

    Node() : next(nullptr) {}
    Node(SET<int, OTHER> d) : data(d), next(nullptr) {}
};

template <class OTHER>
void bucketSort(Node<OTHER> *& p) {
    Node<OTHER> *bucket[10], *last[10], *tail;
    int i, j, k, base = 1, max = 0, digits = 0;
    for (tail = p; tail != nullptr; tail = tail->next) {
        if (tail->data.key > max) max = tail->data.key; // 找到最大值
    }
    // 找最大键值的位数
    do {
        max /= 10;
        digits++;
    } while (max > 0);

    for (i = 1; i <= digits; i++) {
        for (j = 0; j <= 9; j++) bucket[j] = last[j] = nullptr; // 初始化口袋
        while (p != nullptr) {
            Node<OTHER> *current = p; // 摘下链表头结点
            p = p->next;
            current->next = nullptr;

            k = (current->data.key / base) % 10; // 取出当前位的数字
            if (bucket[k] == nullptr) {
                bucket[k] = last[k] = current;
            } else {
                last[k]->next = current; // 追加到对应口袋尾部，保持稳定性
                last[k] = current;
            }
        }

        tail = nullptr;
        for (j = 0; j <= 9; j++) {
            if (bucket[j] == nullptr) continue;
            if (p == nullptr) {
                p = bucket[j]; // 第一个非空口袋成为新链表头
            } else {
                tail->next = bucket[j]; // 后续口袋接到链表尾部
            }
            tail = last[j];
        }
        if (tail != nullptr) tail->next = nullptr; // 表尾置空
        base *= 10; // 为下一次分配做准备
    }
}

性能分析

空间：所需的额外空间只有 10 个链表的头尾指针，与排序元素数量无关，空间复杂度为 $O(1)$ 。
时间：$(一趟分配+ 回收)\times 分配趟数 $，时间复杂度为 $O(len \cdot (n + 10))$ ，即 $O(n \cdot len)$ 。其中 $len$ 为最大键值的位数。稳定的排序算法。