基于比较的排序

排序将记录按关键字重排。比较排序只通过关键字比较获得次序，在一般模型下最坏时间下界为 O(n log n)。稳定排序会保持相等关键字原有的相对顺序；原地排序的额外空间很小。

冒泡、选择与插入排序

• 冒泡排序：相邻逆序就交换，每一趟把最大值送到末尾。稳定、原地，平均和最坏 O(n²)；加入交换标志后，已排序数据最好 O(n)。
• 选择排序：每轮从未排序区选最小元素交换到前端。比较次数固定为 O(n²)，原地，交换可能改变相等元素的先后，通常不稳定。
• 插入排序：将当前元素插入已排序前缀。稳定、原地，平均 O(n²)，近乎有序时最好 O(n)。

void insertionSort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); ++i) {
        int x = a[i], j = i - 1;
        while (j >= 0 && a[j] > x) a[j + 1] = a[j--];
        a[j + 1] = x;
    }
}

希尔、归并与快速排序

希尔排序按逐渐缩小的间隔进行插入排序，性能取决于增量序列，通常不稳定。归并排序递归分半并合并两个有序段，稳定，时间始终为 O(n log n)，但需要 O(n) 辅助空间。快速排序选择基准并分区，平均 O(n log n)、原地且通常不稳定；极端划分会退化为 O(n²)，可随机选择基准或三路划分降低风险。

堆排序与选择

堆排序先建最大堆，再重复取堆顶并下沉调整，时间 O(n log n)、额外空间 O(1)、不稳定，且最坏界有保证。实际编程优先使用 sort；需要稳定性使用 stable_sort。小规模或近乎有序数据适合插入排序，要求稳定可选归并排序，要求 O(n log n) 最坏界且空间受限可选堆排序。