以下是几种常见排序算法的 JS实现，包括选择排序、冒泡排序、插入排序、快速排序和归并排序，以及每种算法的特点和复杂度分析
1. 选择排序（Selection Sort）
核心思想：每次从未排序部分选择最小元素，与未排序部分的第一个元素交换。
function selectionSort(arr) {const n = arr.length;for (let i = 0; i < n - 1; i++) {let minIndex = i;// 找到未排序部分的最小元素索引for (let j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换最小元素到当前位置if (minIndex !== i) {[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];}}return arr;
}
特点：
- 时间复杂度：O(n²)，无论数据分布如何。
- 空间复杂度：O(1)，原地排序。
- 稳定性：不稳定（例如
[5, 5, 2]排序后第一个 5 可能被交换到第二个 5 之后）。
2. 冒泡排序（Bubble Sort）
核心思想：多次遍历数组，比较相邻元素并交换，将最大元素“冒泡”到末尾。
function bubbleSort(arr) {const n = arr.length;for (let i = 0; i < n - 1; i++) {let swapped = false;for (let j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];swapped = true;}}// 如果没有交换，说明数组已排序，提前退出if (!swapped) break;}return arr;
}
特点：
- 时间复杂度：O(n²)，优化后最好情况为 O(n)（数据已排序）。
- 空间复杂度：O(1)，原地排序。
- 稳定性：稳定（相同元素的相对顺序不变）。
3. 插入排序（Insertion Sort）
核心思想：将未排序数据插入已排序序列的合适位置。
function insertionSort(arr) {const n = arr.length;for (let i = 1; i < n; i++) {const current = arr[i];let j = i - 1;// 将大于current的元素后移while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];j--;}// 插入currentarr[j + 1] = current;}return arr;
}
特点：
- 时间复杂度：O(n²)，最好情况为 O(n)（数据接近有序）。
- 空间复杂度：O(1)，原地排序。
- 稳定性：稳定。
- 适用场景：小规模数据或部分有序数据。
4. 快速排序（Quick Sort）
核心思想：分治法，选择基准值，将数组分为两部分，递归排序。
function quickSort(arr) {if (arr.length <= 1) return arr;const pivot = arr[0]; // 选择第一个元素为基准const left = [];const right = [];for (let i = 1; i < arr.length; i++) {if (arr[i] <= pivot) {left.push(arr[i]);} else {right.push(arr[i]);}}return [...quickSort(left), pivot, ...quickSort(right)];
}
特点：
- 时间复杂度：平均 O(n log n)，最坏 O(n²)（如基准选择不当）。
- 空间复杂度：O(log n)（递归栈），非原地版本为 O(n)。
- 稳定性：不稳定。
- 优化：随机选择基准、三路快排（处理重复元素）。
5. 归并排序（Merge Sort）
核心思想：分治法，将数组分成两半，分别排序后合并。
function mergeSort(arr) {if (arr.length <= 1) return arr;const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid));const right = mergeSort(arr.slice(mid));return merge(left, right);
}function merge(left, right) {const result = [];let i = 0, j = 0;while (i < left.length && j < right.length) {if (left[i] <= right[j]) {result.push(left[i]);i++;} else {result.push(right[j]);j++;}}return [...result, ...left.slice(i), ...right.slice(j)];
}
特点：
- 时间复杂度：O(n log n)，稳定且不受数据分布影响。
- 空间复杂度：O(n)（辅助数组）。
- 稳定性：稳定。
- 适用场景：大规模数据、外部排序。
复杂度对比表
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
使用示例
const arr = [5, 3, 8, 4, 2];
console.log(selectionSort([...arr])); // [2, 3, 4, 5, 8]
console.log(bubbleSort([...arr])); // [2, 3, 4, 5, 8]
console.log(insertionSort([...arr])); // [2, 3, 4, 5, 8]
console.log(quickSort([...arr])); // [2, 3, 4, 5, 8]
console.log(mergeSort([...arr])); // [2, 3, 4, 5, 8]
注意：为避免修改原数组，传入排序函数前使用 [...arr] 复制数组。实际开发中推荐使用 JavaScript 内置的 Array.prototype.sort()，其底层基于优化的快速排序或归并排序，时间复杂度为 O(n log n)。
