用js实现常见排序算法

以下是几种常见排序算法的 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)。