排序算法分类
按排序思想可以分为： 插入排序、交换排序、选择排序、归并排序、基数排序。
时间复杂度： 常见比较排序的平均时间复杂度有 O(n²) 和 O(n log₂ n) 等。具体分析需要区分最好、平均和最坏情况；希尔排序还取决于增量序列，基数排序则取决于记录数、位数和基数。
稳定性： 若排序后，关键字相等的记录仍保持原来的相对顺序，则称该排序算法是稳定的。
例如按数值关键字排序时，[2A, 1, 2B] 的稳定排序结果是 [1, 2A, 2B]，两个关键字为 2 的记录仍按 A、B 排列。字母只用于标识记录，不参与比较；这些标记是概念示例，不是 JavaScript 数值。
以下代码按数值升序排序，除特别说明外，会直接修改传入的数组。
各代码块可独立运行。比较排序示例假定输入为稠密数组（没有空位），每个元素均为有限的 Number，不包含 NaN；示例不重复校验这些前置条件。基数排序的输入范围和校验在对应章节说明。
插入排序
基本思想：
每一步将一个待排序的记录，按其关键字大小插入前面已排序区间的适当位置，直到所有记录有序。
具体实现的3️⃣种不同算法：
- 直接插入排序：顺序查找插入位置，实现简单。
- 折半插入排序：折半查找插入位置。
- 希尔排序：按逐趟缩小的增量进行插入排序。
1️⃣直接插入排序
排序过程： 对非空数组进行 n-1 趟插入：将第 1 个记录看成有序区间，从第 2 个记录开始逐个插入，直至整个数组有序。
function insertionSort(L) {
for (let i = 1; i < L.length; i++) {
if (L[i] < L[i - 1]) {
const temp = L[i];
let j = i - 1;
while (j >= 0 && temp < L[j]) {
L[j + 1] = L[j];
--j;
}
L[j + 1] = temp;
}
}
return L;
}
console.log(insertionSort([2,6,3,1,4])); // [1,2,3,4,6]算法分析：
时间复杂度： 已有序时最好为 O(n)，平均和最坏为 O(n²)。
额外空间复杂度： O(1)。
稳定性： 稳定，只移动关键字严格大于待插入记录的元素，不改变相等记录的相对顺序。
2️⃣折半插入排序
排序过程： 插入 L[i] 时，利用折半查找在前面的有序区间中寻找插入位置，再向后移动元素以腾出位置。为保持稳定性，相等时继续向右查找，将新记录放在已有相等记录之后。
function binaryInsertionSort(L) {
for (let i = 1; i < L.length; ++i) {
const temp = L[i];
let low = 0;
let high = i - 1;
while (low <= high) {
const m = low + Math.floor((high - low) / 2);
if (temp < L[m]) {
high = m - 1;
} else {
low = m + 1;
}
}
// 查找结束时 low = high + 1，即插入位置
for (let j = i; j > low; --j) {
L[j] = L[j - 1];
}
L[low] = temp;
}
return L;
}
console.log(binaryInsertionSort([8,2,3,1,5,6,4]));算法分析：
减少了定位插入位置所需的比较次数，但没有减少元素移动次数。实际性能取决于输入是否有序，以及比较和移动的成本。
时间复杂度： 本实现即使输入已有序，也会逐次执行折半查找，最好为 O(n log₂ n)；平均和最坏仍为 O(n²)。
额外空间复杂度： O(1)。
稳定性： 稳定，相等时向右查找，保留相等记录的原有顺序。
3️⃣希尔排序
基本思想：
将相隔增量 dk 的记录组成一个子序列，分别进行直接插入排序；这里的分组不是连续分段。逐趟缩小增量，最后以增量 1 对全体记录进行直接插入排序。
排序过程： 下图和代码默认采用 3、2、1。前几趟通过跨位置移动减少逆序，最后一趟完成全局排序。采用合适的增量序列时，通常可以减少直接插入排序所需的移动，实际性能取决于增量和输入。
图中初始序列为 21、25、49、25*、16、08，星号用于区分两个关键字同为 25 的记录。排序后 25* 出现在普通 25 之前，说明希尔排序不稳定。
增量参数 gaps 必须是非空数组，各增量为正安全整数、严格递减，且最后一个为 1。函数先校验整个增量序列，再修改输入数组，避免错误参数导致部分排序或返回未排序的结果。
function shellSort(L, gaps = [3, 2, 1]) {
const message = "增量序列必须为正安全整数、严格递减并以 1 结尾";
if (!Array.isArray(gaps) || gaps.length === 0 || gaps[gaps.length - 1] !== 1) {
throw new RangeError(message);
}
let previous = Infinity;
for (const gap of gaps) {
if (!Number.isSafeInteger(gap) || gap <= 0 || gap >= previous) {
throw new RangeError(message);
}
previous = gap;
}
for (const gap of gaps) {
shellInsert(L, gap); // 按当前增量进行一趟插入排序
}
return L;
}
function shellInsert(L, dk) {
for (let i = dk; i < L.length; ++i) {
if (L[i] < L[i - dk]) {
const temp = L[i];
let j = i - dk;
while (j >= 0 && temp < L[j]) {
L[j + dk] = L[j];
j -= dk;
}
L[j + dk] = temp;
}
}
}
console.log(shellSort([21,25,49,25,16,8], [3,2,1])); // [8,16,21,25,25,49]算法分析：
时间复杂度： 取决于记录数 n 和增量序列，不能统一写成某个经验幂次。本文固定使用 3、2、1 时，已有序输入最好为 O(n)，平均（随机排列）和最坏均为 O(n²)：第一趟对 3 个长度约为 n/3 的子序列进行直接插入排序，其平均和最坏工作量就已是二次量级。自定义 m 个增量时，校验还需要 O(m) 时间。
额外空间复杂度： O(1)。
稳定性： 不稳定，跨位置移动可能改变相等记录的相对顺序。
默认增量用于配合图示演示；较长数组应结合理论分析和实际表现选择增量序列。希尔排序依赖按下标访问相隔增量的元素，不适合直接用于链表。
交换排序
基本思想：
两两比较，如果发生逆序则交换，直到所有记录都排好序为止。
1️⃣冒泡排序
排序过程： 从左到右比较相邻记录，出现逆序就交换，使当前未排序区间的最大值移到末尾。每趟缩小一个位置；某趟没有交换时，说明数组已有序，可以提前结束。
function bubbleSort(L) {
let m = L.length - 1;
let flag = true;
while (m > 0 && flag) {
flag = false;
for (let j = 0; j < m; j++) {
if (L[j] > L[j + 1]) { // 从小到大排
flag = true;
[L[j], L[j + 1]] = [L[j + 1], L[j]]; // 交换数据
}
}
m--;
}
return L;
}
console.log(bubbleSort([21,25,49,25,16,18,9,88,7,3,6,30]));算法分析：
设记录数为 n，比较次数和移动次数与初始排列有关。
最好情况： 已有序时只需一趟检查，比较 n-1 次且不交换，时间为 O(n)。
最坏情况： 逆序时需要 n(n-1)/2 次比较和交换，时间为 O(n²)。
平均时间复杂度： O(n²)。
额外空间复杂度： O(1)。
稳定性： 稳定，相等记录不会互换。
2️⃣快速排序
基本思想：
选择一个元素（如第一个）作为基准值（pivot）。
通过一次划分，将基准放到最终位置，左侧元素不大于基准，右侧元素不小于基准。再递归排序左右子序列，直到子序列只剩一个元素或为空。
本文快速排序实现的特点：
- 首元素作为基准，两个下标从两端向中间交替扫描并交换记录，完成一次划分。这是本文采用的划分方式，其他实现也可以使用不同方式。
- 递归排序基准两侧的子序列，子序列为空或只有一个元素时结束。
// 快排
function quickSort(L, low = 0, high = L.length - 1) {
if (low < high) {
const pivotloc = partition(L, low, high);
quickSort(L, low, pivotloc - 1);
quickSort(L, pivotloc + 1, high);
}
return L;
}
// 快速排序的一次划分
function partition(L, low, high) {
const pivotkey = L[low];
while (low < high) {
while (low < high && L[high] >= pivotkey) {
--high;
}
[L[low], L[high]] = [L[high], L[low]]; // 交换两个位置
while (low < high && L[low] <= pivotkey) {
++low;
}
[L[low], L[high]] = [L[high], L[low]]; // 交换位置
}
return low;
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(quickSort(L));算法分析：
时间复杂度： 各次划分均衡时，最好为 O(n log₂ n)；在关键字互异且输入随机排列的假设下，平均也为 O(n log₂ n)。实际性能受基准选择、输入顺序和重复关键字数量影响。
最坏时，每次基准都是当前子序列的最小值或最大值，仅排除一个元素。各次划分的工作量依次约为 n-1、n-2、…、1，总时间为 O(n²)。本文选择首元素为基准，已有序、逆序或全部相等的输入都会导致这种退化。
额外空间复杂度： 划分过程为 O(1)，递归栈空间取决于递归树高度；在上述随机排列假设下，平均为 O(log₂ n)，最坏为 O(n)。
稳定性： 不稳定，跨位置交换可能改变相等记录的相对顺序。
本例用于演示首元素基准的递归实现。较大的退化输入还可能导致 JavaScript 调用栈溢出；实际应用中可结合随机基准、针对重复关键字的三路划分，以及只递归较短一侧、循环处理较长一侧等方式改进。
选择排序
基本思想：
每一趟从尚未排序的区间中选出关键字最小或最大的记录，使有序区间增加一个元素。简单选择排序直接查找最小值，堆排序则利用堆结构取得最大值。
1️⃣简单选择排序
排序过程： 每趟找到最小记录后，将其与尚未排序区间的第一个记录交换。
function selectionSort(L) {
for (let i = 0; i < L.length - 1; i++) {
let k = i;
for (let j = i + 1; j < L.length; j++) {
if (L[j] < L[k]) {
k = j;
}
}
if (k !== i) {
[L[i], L[k]] = [L[k], L[i]];
}
}
return L;
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(selectionSort(L));算法分析：
每趟至多交换一次，总交换次数至多为 n-1。若按一次交换相当于 3 次记录赋值的传统计数方式计算移动次数：
最少移动次数： 0。
最多移动次数： 3(n-1)。
时间复杂度： 最好、平均和最坏均为 O(n²)，比较次数为 n(n-1)/2。
额外空间复杂度： O(1)。
稳定性： 不稳定。例如 [2A, 2B, 1C] 第一趟交换后变为 [1C, 2B, 2A]，两个关键字为 2 的记录顺序发生变化。
2️⃣堆排序
堆可以用数组表示为完全二叉树。大顶堆要求每个父结点的值不小于其子结点，小顶堆则要求父结点的值不大于其子结点；堆并不要求左右子树之间有大小关系。
大顶堆的根结点是最大值。将其与有效堆范围内的最后一个元素交换，把最大值放入数组末尾的已排序区；缩小堆的范围，再恢复大顶堆。重复此过程，得到升序数组。
如何将堆顶移到末尾后，恢复大顶堆？
- 交换堆顶与末尾元素，排除末尾已排序元素，新的根结点可能需要下沉。
- 比较当前结点的两个孩子，选择较大的一个；若孩子更大，则交换，并移动到该孩子的位置继续检查。
- 当前结点不小于孩子，或已没有孩子时，调整结束。
上图演示的是初始建堆：从最后一个非叶子结点 42 开始，自底向上调整。最后调整根结点时，46 先与 94 交换，再沿左子树与 70 交换。交换后需要继续向下检查，才能恢复整个子树的堆性质。
// 大顶堆
function adjustHeap(L, i, length) {
let k = i * 2 + 1; // 当前结点的左孩子
while (k < length) {
if (k + 1 < length && L[k] < L[k + 1]) {
++k; // 选择较大的孩子
}
if (L[i] >= L[k]) {
break;
}
[L[i], L[k]] = [L[k], L[i]];
i = k; // 沿交换后的孩子位置继续下沉
k = i * 2 + 1;
}
}
function heapSort(arr) {
// 从最后一个非叶子结点开始，自底向上构建大顶堆
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; --i) {
adjustHeap(arr, i, arr.length);
}
// 交换堆顶与末尾元素，缩小有效堆的范围并重新调整
for (let j = arr.length - 1; j > 0; --j) {
[arr[0], arr[j]] = [arr[j], arr[0]];
adjustHeap(arr, 0, j);
}
return arr;
}
const arr = [46,55,13,42,94,5,17,70];
console.log(heapSort(arr));算法分析：
时间复杂度： 自底向上建堆需要 O(n) 时间；每次取出堆顶后，调整至多需要 O(log₂ n) 时间，整体最坏为 O(n log₂ n)。本实现全相等时下沉立即结束，最好为 O(n)；平均为 O(n log₂ n)。
额外空间复杂度： O(1)。
稳定性： 不稳定，堆顶与末尾元素的交换可能改变相等记录的相对顺序。
归并排序（二路归并）
基本思想： 将两个有序子序列合并为一个新的有序序列。
排序过程： 本文代码采用自顶向下递归：先把数组拆成左右两半，分别排序，再合并两个有序数组。数组为空或只有一个元素时直接返回副本。
也可以自底向上：将初始数组看成 n 个长度为 1 的有序子序列，两两合并，第一趟得到 ⌈n/2⌉ 个长度为 2 或 1 的子序列，再逐趟合并，直至整个数组有序；⌈n/2⌉ 表示向上取整。
以下实现通过两个下标合并有序数组，不反复删除数组首项，并返回新数组，保留原数组。
// 归并排序
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
while (i < left.length) result.push(left[i++]);
while (j < right.length) result.push(right[j++]);
return result;
}
function mergeSort(items) {
if (items.length <= 1) {
return items.slice();
}
const middle = Math.floor(items.length / 2);
const left = items.slice(0, middle);
const right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(mergeSort(L));算法分析：
时间复杂度： 本文常规实现的最好、平均和最坏均为 O(n log₂ n)。
额外空间复杂度： O(n)，用于合并数组；递归栈另需 O(log₂ n)，总额外空间仍为 O(n)。
稳定性： 稳定，合并时相等的关键字优先取左侧记录。
基数排序
前面的排序方法主要通过比较关键字来确定顺序。基数排序按各位关键字进行“分配”和“收集”，不直接比较完整关键字之间的大小。
按关键字的处理顺序可以分为：
- 最高位优先 MSD（Most Significant Digit first）。
- 最低位优先 LSD（Least Significant Digit first）。
按存储结构： 可以使用数组桶或链表。链式基数排序是使用链表的实现方式，本节按 LSD 顺序讲解。
下面给出十进制 LSD 基数排序的数组桶实现，仅支持由非负安全整数组成的稠密数组（每个数值在 0 到 Number.MAX_SAFE_INTEGER 之间），返回新数组，保留原数组。数组长度直接从 data.length 取得，桶数量由基数 10 决定。
使用 for...of 校验每个元素，空位会被读为 undefined 并拒绝；some() 等跳过空位的方法无法完成这项校验。
// 求数组中数值的最大十进制位数，0 按一位处理
function maxDigits(data) {
let digits = 1;
let threshold = 10;
for (const value of data) {
while (value >= threshold) {
threshold *= 10;
++digits;
}
}
return digits;
}
function radixSort(data) {
if (!Array.isArray(data)) {
throw new TypeError("基数排序的输入必须是数组");
}
for (const value of data) {
if (!Number.isSafeInteger(value) || value < 0) {
throw new RangeError("基数排序仅支持由非负安全整数组成的稠密数组");
}
}
let result = data.slice();
if (result.length <= 1) return result;
const digits = maxDigits(result);
const base = 10;
let place = 1; // 依次处理个位、十位、百位……
for (let i = 0; i < digits; ++i) {
const buckets = Array.from({ length: base }, () => []);
for (const value of result) {
const digit = Math.floor(value / place) % base;
buckets[digit].push(value); // 保持相同位值记录的原有顺序
}
const next = [];
for (const bucket of buckets) {
for (const value of bucket) next.push(value);
}
result = next;
place *= base;
}
return result;
}
const L = [21,25,49,25,16,18,9,88,7,3,6,30];
console.log(radixSort(L)); // [3,6,7,9,16,18,21,25,25,30,49,88]算法分析： 设记录数为 n，最大位数为 d，基数为 r。
时间复杂度： 每趟分配 n 个记录并收集 r 个桶，共 d 趟，为 O(d(n + r))；输入校验需要 O(n) 时间，不改变整体复杂度。
额外空间复杂度： O(n + r)。
稳定性： 稳定，桶内按原顺序加入和收集，每趟都保留相同位值记录的相对顺序。
1️⃣最高位优先法（MSD）
先按最高位关键字 k₁ 分组，再在各组内按次高位关键字 k₂ 继续分组，依次处理到最低位，最后按组的顺序连接。
十进制数可以看作多关键字记录，位数不足时在前面补 0。下文的 063、008 仅用于补零显示，JavaScript 数值应写作 63、8。
以下用 MSD 顺序排序：
按最高位排序
{063，064，008，083}，{109，184}，{278，269}，{589，505}，
在各组内按次高位排序
{008},{063,064},{083},{109},{184},{269},{278},{505},{589},
按最低位排序
{008},{063},{064},{083},{109},{184},{269},{278},{505},{589},
最后将所有的子序列依次链接在一起就得到排好的序列
2️⃣最低位优先法（LSD）
先按最低位排序，再按次低位排序，直到处理完最高位。每一趟都对整个序列排序。
关键条件： 每一趟排序必须稳定，才能保留前面低位排序的结果。本节代码通过桶内顺序追加、顺序收集来保证稳定性。
最低位优先法
278，109，063，930，184，589，269，008，083
按个位排序
930，063，083，184，278，008，109，589，269
按十位排序
008，109，930，063，269，278，083，184，589
按百位排序
008，063，083，109，184，269，278，589，930
链式基数排序
先决条件：
- 知道各级关键字的主次关系
- 知道各级关键字的取值范围
利用“分配”和“收集”对关键字进行排序：
首先处理最低位，各个记录按照此位关键字的值“分配”到相应的链式队列中，同一队列的记录按原顺序入队。
按照位值从小到大依次连接各队列，完成“收集”，然后继续处理下一位。使用队列的先进先出顺序，保证每一趟分配和收集稳定。
算法分析： 与前述数组桶实现一样，时间复杂度为 O(d(n + r))，额外空间为 O(n + r)，稳定性由队列的顺序入队和收集保证。采用静态链表表示时，可使用 n 个记录链接位置，以及 r 个队列的头、尾指针，共 n + 2r 个附加链接位置。
排序算法比较
以下对照本文的实现。额外空间包含递归栈；基数排序中 d 为最大位数，r 为基数。
| 排序方法 | 最好时间 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 | 修改原数组 |
|---|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 折半插入排序 | O(n log₂ n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 希尔排序（增量 3、2、1） | O(n) | O(n²) | O(n²) | O(1) | 不稳定 | 是 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 快速排序 | O(n log₂ n) | O(n log₂ n) | O(n²) | 平均 O(log₂ n)，最坏 O(n) | 不稳定 | 是 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 是 |
| 堆排序 | O(n)（全相等时） | O(n log₂ n) | O(n log₂ n) | O(1) | 不稳定 | 是 |
| 归并排序 | O(n log₂ n) | O(n log₂ n) | O(n log₂ n) | O(n) | 稳定 | 否 |
| LSD 基数排序 | O(d(n + r)) | O(d(n + r)) | O(d(n + r)) | O(n + r) | 稳定 | 否 |
希尔排序一行对应本文默认的固定增量，平均时间按随机排列分析；更换增量序列时需要重新分析。快速排序的平均复杂度采用前文的关键字互异、随机排列假设。堆排序的 O(n) 最好时间对应本文全相等时提前结束下沉的实现。
原地修改的方法返回传入的数组；归并排序和基数排序始终返回新数组，包括空数组和单元素数组。
选择时可以结合这些特点：
- 数组较小或接近有序时，可考虑直接插入排序；若比较成本较高，折半插入可以减少查找插入位置的比较次数，但仍需移动元素。
- 需要最坏 O(n log₂ n) 的比较排序时，可以考虑堆排序或归并排序；归并排序还保持稳定性，并需要 O(n) 额外空间。
- 非负安全整数且位数有限时，可以考虑本文的 LSD 基数排序，同时评估桶所需的额外空间。希尔排序和快速排序的表现则需要结合增量或基准策略、输入分布来判断。