在JavaScript中，常见的排序算法有以下几种：
1. 冒泡排序 (Bubble Sort)
- 时间复杂度: O(n²)
- 空间复杂度: O(1)
- 原理: 相邻元素比较交换，大的元素逐渐”冒泡”到数组末尾
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
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]];
}
}
}
return arr;
}2. 选择排序 (Selection Sort)
- 时间复杂度: O(n²)
- 空间复杂度: O(1)
- 原理: 每次选择最小元素放到已排序部分的末尾
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}3. 插入排序 (Insertion Sort)
- 时间复杂度: O(n²)
- 空间复杂度: O(1)
- 原理: 将元素插入到已排序部分的正确位置
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}4. 快速排序 (Quick Sort)
- 时间复杂度: 平均O(n log n)，最坏O(n²)
- 空间复杂度: O(log n)
- 原理: 选择基准元素，将数组分割成小于和大于基准的两部分
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}5. 归并排序 (Merge Sort)
- 时间复杂度: O(n log n)
- 空间复杂度: O(n)
- 原理: 分治法，将数组分成两半分别排序后合并
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) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}6. 堆排序 (Heap Sort)
- 时间复杂度: O(n log n)
- 空间复杂度: O(1)
- 原理: 构建最大堆，然后逐个提取最大元素
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, 0, i);
}
return arr;
}
function buildMaxHeap(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, i, n);
}
}
function heapify(arr, i, heapSize) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let largest = i;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, largest, heapSize);
}
}7. 计数排序 (Counting Sort)
- 时间复杂度: O(n + k)，k为数据范围
- 空间复杂度: O(k)
- 原理: 统计每个元素出现次数，适用于整数排序
function countingSort(arr) {
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
const count = new Array(range).fill(0);
const output = new Array(arr.length);
// 统计每个元素出现次数
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 计算累积计数
for (let i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 构建输出数组
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}8. JavaScript内置排序 (Array.prototype.sort)
JavaScript提供了内置的排序方法，通常使用高效的混合算法（如Timsort）：
// 默认按字符串排序
arr.sort();
// 数字排序
arr.sort((a, b) => a - b);
// 自定义比较函数
arr.sort((a, b) => {
// 返回负数：a < b
// 返回0：a = b
// 返回正数：a > b
});性能对比总结
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(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 log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |