排序算法

1. 内部排序

算法	平均时间	最坏情况	辅助存储	稳定性
冒泡顺序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n\log{n})$	$O(n\log^2{n})$	$O(1)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
归并排序	$O(n\log{n})$	$O(n\log{n})$	$O(n)$	稳定
快速排序	$O(n\log{n})$	$O(n^2)$	$O(\log{n})$	不稳定
堆排序	$O(n\log{n})$	$O(n\log{n})$	$O(1)$	不稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n+k)$	稳定
基数排序	$O(n \times k)$	$O(n \times k)$	$O(n+k)$	稳定

1.1 冒泡排序

Bubble Sort

#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    for (long i = 0; i < arr.size(); i++) {
        bool flag = true;
        for (long j = 0; j < arr.size() - i - 1; j++)
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                flag = false;
            }
        if (flag == true) return;
    }
}

1.2 插入排序

Insert Sort

#include <vector>
using namespace std;

void insertSort(vector<int>& arr) {
    // 插入排序将序列分为已排序的前缀和未排序的后缀
    // 插入排序每次从后缀中选取一个元素,然后将其插入已有序的前缀
    for (long i = 1; i < arr.size(); i++) {
        // arr[i] denotes the current target to be inserted into the sorted
        // prefix, and j moves in the sorted prefix from the maximum to minimum
        int target = arr[i];
        long j = i - 1;
        while (j >= 0)
            // 如果待插入对象target位于arr[j]左侧,应继续移动
            if (target < arr[j]) {
                arr[j + 1] = arr[j];
                --j;
            } else  // 已找到待插入对象应该插入的位置
                break;
        arr[j + 1] = target;
    }
}

1.3 希尔排序

1.4 选择排序

Select Sort

#include <vector>
using namespace std;

void selectSort(vector<int>& arr) {
    // 选择排序将序列分为无序的前缀和有序的后缀,且前缀中的所有元素都比后缀中的元素要小
    // 每次选择前缀中的最大值,然后插入后缀的首元素之前即可
    for (long i = arr.size() - 1; i >= 0; --i) {
        int max = arr[i];  // 先假定无序前缀的最大值为其最后一个元素
        long rank = i;                // 最大值对应的秩
        for (long j = 0; j < i; j++)  // 在无序前缀中寻找真正的最大值
            if (arr[j] >= max) {
                max = arr[j];
                rank = j;
            }
        swap(arr[rank], arr[i]);  // 更新
    }
}

1.5 归并排序

Merge Sort

#include <vector>
using namespace std;

void merge(vector<int>&, long, long, long);           // 声明
void mergeSort(vector<int>& arr, long lo, long hi) {  // 左闭右开[lo, hi)
    if (hi - lo < 2) return;  // 单元素区间自然有序
    long mi = (lo + hi) / 2;
    mergeSort(arr, lo, mi);  // 排序左区间[lo, mi)
    mergeSort(arr, mi, hi);  // 排序右区间[mi, hi)
    merge(arr, lo, mi, hi);  // 归并
}

void merge(vector<int>& arr, long lo, long mi, long hi) {
    long frontLen = mi - lo;  // 前(左）子向量的长度
    auto frontCopy = new int[frontLen];
    for (long i = 0; i < frontLen; i++)  // 复制前（左）子向量
        frontCopy[i] = arr[lo + i];
    long i = lo, l = 0, r = mi;  // index of total, left, right vector
    while (i < hi) {
        if (r >= hi || (l < frontLen && frontCopy[l] <= arr[r]))
            arr[i++] = frontCopy[l++];
        if (l >= frontLen || (r < hi && arr[r] < frontCopy[l]))
            arr[i++] = arr[r++];
    }
    delete[] frontCopy;
}

上述merge函数中的while (i < hi) {}循环体稍显晦涩，可等效地拆解为如下三个部分：

    while (l < frontLen && r < hi) {
        if (frontCopy[l] <= arr[r])
            arr[i++] = frontCopy[l++];
        else {
            count += r - mi + 1;
            arr[i++] = arr[r++];
        }
    }
    while (l < frontLen) arr[i++] = frontCopy[l++];  // 前子向量未处理完时
    while (r < hi) arr[i++] = arr[r++];  // 后子向量未处理完时

1.6 快速排序

Quick Sort

#include <vector>
using namespace std;

long partition(vector<int>&, long, long);  // 声明
void quickSort(vector<int>& arr, long lo, long hi) {
    if (hi - lo < 2) return;  // 单元素区间自然有序
    // 在[lo, hi)内构造支(轴)点,将原向量分割为两部分
    // 轴点的作用是,其左侧的元素均不大于轴点元素,其右侧的值均不小于轴点值
    long mi = partition(arr, lo, hi);
    quickSort(arr, lo, mi);      // 对前缀递归排序
    quickSort(arr, mi + 1, hi);  // 对后缀递归排序
}
long partition(vector<int>& arr, long lo, long hi) {  // 轴点构造算法
    // 任选一个元素与首元素交换
    long rank = lo + rand() % (hi - lo);
    swap(arr[lo], arr[rank]);

    int pivot = arr[lo];  // 以首元素为候选支(轴)点——经以上交换，等效于随机选取
    while (lo < hi - 1) {
        while (lo < hi - 1 && pivot <= arr[hi - 1]) --hi;  // 向左扩展右端子向量
        arr[lo] = arr[hi - 1];
        while (lo < hi - 1 && arr[lo] <= pivot) ++lo;  // 向右扩展左端子向量
        arr[hi - 1] = arr[lo];  // 大于pivot者归入右侧子序列
    }                           // assert: lo == hi - 1
    arr[lo] = pivot;  // 将备份的轴点记录置于前、后子向量之间
    return lo;  // 返回轴点的秩,即母算法中需要的切分点的位置
}

1.7 堆排序

1.8 桶排序

1.9 基数排序

2. 外部排序

To be continued.