当前位置：首页 > news >正文

JS数组排序算法

news 2025/8/11 9:34:59

1. 冒泡排序（Bubble Sort）

原理

从数组头开始，两两比较相邻元素，若顺序错误（比如升序时前面大于后面），就交换它们。
每一趟会把当前未排序部分的最大（或最小）元素“冒泡”到末尾。
重复多趟，直到整个数组有序。

代码示例

function bubbleSort(arr) {let len = arr.length;for (let i = 0; i < len - 1; i++) {// 每趟冒泡，把最大值放到末尾for (let j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换let temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}return arr;
}

时间复杂度
- 平均和最坏：O(n²)
- 最好（数组已基本有序）：O(n)
优缺点
- 简单易懂，代码短。
- 性能较差，尤其大数据量时效率低。
- 稳定排序（相等元素顺序不变）。

2. 插入排序（Insertion Sort）

原理

把数组分成已排序和未排序两部分。
每次取未排序的第一个元素，插入到已排序部分的合适位置。
类似打牌时整理手牌的过程。

代码示例

function insertionSortSeparate(arr) {let sorted = []; // 已排序数组let unsorted = arr.slice(); // 未排序数组，复制一份避免修改原数组while (unsorted.length > 0) {let current = unsorted.shift(); // 取出未排序的第一个元素// 找到插入位置let inserted = false;for (let i = 0; i < sorted.length; i++) {if (current < sorted[i]) {// 插入到第i个位置，后面元素依次后移sorted.splice(i, 0, current);inserted = true;break;}}// 如果比所有已排序元素都大，插入到末尾if (!inserted) {sorted.push(current);}}return sorted;
}

简洁版：

function insertionSort(arr) {let len = arr.length;for (let i = 1; i < len; i++) {let key = arr[i];let j = i - 1;// 向左移动已排序元素，为 key 找合适位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}return arr;
}

时间复杂度
- 平均和最坏：O(n²)
- 最好（几乎有序）：O(n)
优缺点
- 适合部分有序数组，性能比冒泡好一点。
- 稳定排序。
- 代码实现稍复杂。

3. 快速排序（Quick Sort）

原理

选择一个“基准”元素（pivot），通常是中间或第一个元素。
把数组分成两部分：小于基准的和大于基准的。
递归地对两部分分别排序。
最后把排好序的左边 + 基准 + 右边拼起来。

代码示例（递归版）

function quickSort(arr) {if (arr.length <= 1) return arr;let pivotIndex = Math.floor(arr.length / 2);let pivot = arr.splice(pivotIndex, 1)[0];let left = [];let right = [];for (let i = 0; i < arr.length; i++) {if (arr[i] < pivot) left.push(arr[i]);else right.push(arr[i]);}return quickSort(left).concat([pivot], quickSort(right));
}