2025-06-16

000-排序算法

各类排序算法详解（JavaScript版）

以下是常见排序算法的详细解析，包含清晰原理图解、JavaScript实现和性能分析。每种算法均附有可视化说明，帮助理解其运作机制。

1. 冒泡排序（Bubble Sort）

原理：
重复遍历数组，比较相邻元素，如果顺序错误则交换。每轮遍历将最大元素”冒泡”到末尾。

图解：

初始： [5, 3, 8, 4, 2]
第1轮：3 5 4 2 [8]  // 8已就位
第2轮：3 4 2 [5, 8] // 5就位
第3轮：3 2 [4, 5, 8] 
第4轮：[2, 3, 4, 5, 8] // 完成

JavaScript实现：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换相邻元素
      }
    }
  }
  return arr;
}

性能：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定
最佳用例：基本有序的数组

2. 选择排序（Selection Sort）

原理：
每次从未排序部分选择最小元素，与未排序部分的首位交换。

图解：

初始： [5, 3, 8, 4, 2]
第1轮：2 | [3, 8, 4, 5]  // 2就位
第2轮：2, 3 | [8, 4, 5]  // 3就位
第3轮：2, 3, 4 | [8, 5] // 4就位
第4轮：2, 3, 4, 5 | [8] // 完成

JavaScript实现：

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换最小值
  }
  return arr;
}

性能：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定（可能改变相同元素顺序）
特点：交换次数最少

3. 插入排序（Insertion Sort）

原理：
将未排序元素逐个插入已排序部分的正确位置。

图解：

初始： [5, 3, 8, 4, 2]
步骤1： [5] | [3,8,4,2] → [3,5] | [8,4,2]
步骤2： [3,5,8] | [4,2] 
步骤3： [3,4,5,8] | [2] 
步骤4： [2,3,4,5,8]   // 完成

JavaScript实现：

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 后移元素
      j--;
    }
    arr[j + 1] = current; // 插入正确位置
  }
  return arr;
}

性能：

时间复杂度：O(n²)（最佳情况O(n)）
空间复杂度：O(1)
稳定性：稳定
最佳用例：小规模或基本有序数据

4. 快速排序（Quick Sort）

原理：
分治策略。选取基准值（pivot），将数组分为小于基准和大于基准的两部分，递归排序。

图解：

初始： [5, 3, 8, 4, 2]
基准=5 → 分区：[3,4,2] 5 [8] 
递归： [3,4,2] → 基准=3 → [2] 3 [4]
合并： [2,3,4] + 5 + [8] → [2,3,4,5,8]

JavaScript实现：

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++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

性能：

时间复杂度：平均O(n log n)，最坏O(n²)
空间复杂度：O(log n)（递归栈）
稳定性：不稳定
优化：三数取中法选基准

扩展：要在 O(n) 时间复杂度内找出数组中的第 K 个最大元素，可以使用 快速选择算法（Quickselect），它是快速排序的变种，平均时间复杂度为 O(n)，最坏情况下为 O(n²)，但可以通过优化（如随机化 pivot 选择）使其达到 **期望 O(n)**。参考：leetcode 215.数组中的第K个最大元素。

5. 归并排序（Merge Sort）

原理：
分治策略。将数组递归拆分为最小单元，再合并有序子数组。

图解：

拆分： [5,3,8,4,2] → [5,3] [8,4,2] → [5][3] [8][4,2] → [5][3][8][4][2]
合并： [3,5] [2,4,8] → [2,3,4,5,8]  // 按顺序合并子数组

JavaScript实现：

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 = [];
  while (left.length && right.length) {
    left[0] < right[0] 
      ? result.push(left.shift()) 
      : result.push(right.shift());
  }
  return [...result, ...left, ...right];
}

性能：

时间复杂度：O(n log n)
空间复杂度：O(n)（临时数组）
稳定性：稳定
特点：适合链表排序

6. 堆排序（Heap Sort）

原理：
将数组视为完全二叉树，构建最大堆，重复将堆顶元素移到末尾并调整堆。

图解：

初始数组： [5,3,8,4,2]
构建最大堆：     8
             /   \
            4     5
           / \
          3   2
排序步骤： 
  交换堆顶和末尾 → 调整堆 → 重复直到有序

JavaScript实现：

function heapSort(arr) {
  // 构建最大堆
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, arr.length, i);
  }
  
  // 排序
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶和末尾
    heapify(arr, i, 0); // 调整堆
  }
  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

性能：

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定
特点：适合大数据量

关键建议：

小规模数据（<100）：插入排序

通用场景：快速排序

需要稳定性：归并排序

内存敏感：堆排序

7. 希尔排序（Shell Sort）

原理：
改进的插入排序，通过按增量分组进行预排序，最后用插入排序完成最终排序

可视化过程：

原始数组: [9, 8, 7, 6, 5, 4, 3, 2, 1]

增量序列: 4 → 2 → 1

增量4: 分组排序
  [9,5,1] → [1,5,9]
  [8,4]   → [4,8]
  [7,3]   → [3,7]
  [6,2]   → [2,6]
结果: [1,4,3,2,5,8,7,6,9]

增量2: 分组排序
  [1,3,5,7,9] → [1,3,5,7,9]
  [4,2,8,6]   → [2,4,6,8]
结果: [1,2,3,4,5,6,7,8,9]

增量1: 标准插入排序（数组已基本有序）

JavaScript实现：

function shellSort(arr) {
  const n = arr.length;
  
  // 动态计算增量序列（Hibbard序列）
  let gaps = [];
  for (let k = 1; (Math.pow(2, k) - 1) < n; k++) {
    gaps.unshift(Math.pow(2, k) - 1);
  }
  
  for (const gap of gaps) {
    for (let i = gap; i < n; i++) {
      const temp = arr[i];
      let j = i;
      
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      
      arr[j] = temp;
    }
  }
  return arr;
}

性能：

时间复杂度：O(n^{1.25}) ~ O(n^{1.5})
空间复杂度：O(1)
稳定性：✖️
特点：中等规模数据表现优异

8. 计数排序（Counting Sort）

原理：
非比较排序，适用于整数排序，统计每个元素的出现次数

可视化过程：

输入: [4, 2, 2, 8, 3, 3, 1]

创建计数数组:
索引: 0 1 2 3 4 5 6 7 8
计数: 0 1 2 2 1 0 0 0 1

累加计数:
索引: 0 1 2 3 4 5 6 7 8
累加: 0 1 3 5 6 6 6 6 7

反向填充结果数组:
原数组: 4 → 位置6-1=5
原数组: 3 → 位置5-1=4
原数组: 3 → 位置4-1=3
...
结果: [1, 2, 2, 3, 3, 4, 8]

JavaScript实现：

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 (const num of arr) {
    count[num - min]++;
  }
  
  // 累加计数
  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }
  
  // 反向填充结果数组
  for (let i = arr.length - 1; i >= 0; i--) {
    const num = arr[i];
    output[count[num - min] - 1] = num;
    count[num - min]--;
  }
  
  return output;
}

性能：

时间复杂度：O(n + k)（k为数据范围）
空间复杂度：O(n + k)
稳定性：✔️
适用场景：整数排序，数据范围小

9. 桶排序（Bucket Sort）

原理：
将数据分到有限数量的桶里，每个桶再单独排序

可视化过程：

输入: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]

分桶（范围0-1，10个桶）：
桶0: []
桶1: [0.23, 0.25]
桶2: []
桶3: [0.32]
桶4: [0.42, 0.47]
桶5: [0.52, 0.51]
...

每个桶内排序:
桶1: [0.23, 0.25]
桶3: [0.32]
桶4: [0.42, 0.47]
桶5: [0.51, 0.52]

合并结果: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

JavaScript实现：

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return arr;
  
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = Array.from({ length: bucketCount }, () => []);
  
  // 分桶
  for (const num of arr) {
    const bucketIndex = Math.floor((num - min) / bucketSize);
    buckets[bucketIndex].push(num);
  }
  
  // 每个桶排序（使用插入排序）
  const sorted = [];
  for (const bucket of buckets) {
    insertionSort(bucket); // 使用之前实现的插入排序
    sorted.push(...bucket);
  }
  
  return sorted;
}

性能：

时间复杂度：平均O(n + k)，最坏O(n²)
空间复杂度：O(n + k)
稳定性：✔️（取决于桶内排序算法）
适用场景：均匀分布的浮点数

10. 基数排序（Radix Sort）

原理：
按位数分割，从低位到高位依次排序（LSD方法）

可视化过程：

输入: [170, 45, 75, 90, 802, 24, 2, 66]

按个位排序:
0: [170, 90]
2: [802, 2]
4: [24]
5: [45, 75]
6: [66]
→ [170, 90, 802, 2, 24, 45, 75, 66]

按十位排序:
0: [802, 2]
2: [24]
3: []
4: [45]
6: [66]
7: [170, 75]
9: [90]
→ [802, 2, 24, 45, 66, 170, 75, 90]

按百位排序:
0: [2, 24, 45, 66, 75, 90]
1: [170]
8: [802]
→ [2, 24, 45, 66, 75, 90, 170, 802]

JavaScript实现：

function radixSort(arr) {
  const max = Math.max(...arr);
  const maxDigitCount = Math.floor(Math.log10(max)) + 1;
  
  for (let digit = 0; digit < maxDigitCount; digit++) {
    const buckets = Array.from({ length: 10 }, () => []);
    const divisor = Math.pow(10, digit);
    
    // 分桶
    for (const num of arr) {
      const bucketIndex = Math.floor(num / divisor) % 10;
      buckets[bucketIndex].push(num);
    }
    
    // 合并桶
    arr = [].concat(...buckets);
  }
  
  return arr;
}

性能：

时间复杂度：O(d*(n+k))（d为最大位数）
空间复杂度：O(n + k)
稳定性：✔️
适用场景：整数或字符串排序

特殊用途排序算法

11. 鸽巢排序（Pigeonhole Sort）

原理：
适用于数据范围等于数据数量的情况

function pigeonholeSort(arr) {
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;
  const holes = new Array(range).fill(0);
  
  // 统计频率
  for (const num of arr) {
    holes[num - min]++;
  }
  
  // 重建数组
  let index = 0;
  for (let i = 0; i < range; i++) {
    while (holes[i]-- > 0) {
      arr[index++] = i + min;
    }
  }
  return arr;
}

12. 梳排序（Comb Sort）

原理：
冒泡排序的改进，通过设置间隔因子减少小元素在末尾的影响

function combSort(arr) {
  const shrink = 1.3;
  let gap = arr.length;
  let sorted = false;
  
  while (!sorted) {
    gap = Math.floor(gap / shrink);
    if (gap <= 1) {
      gap = 1;
      sorted = true;
    }
    
    for (let i = 0; i + gap < arr.length; i++) {
      if (arr[i] > arr[i + gap]) {
        [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
        sorted = false;
      }
    }
  }
  return arr;
}

13. 鸡尾酒排序（Cocktail Shaker Sort）

原理：
双向冒泡排序，交替方向遍历数组

function cocktailShakerSort(arr) {
  let swapped = true;
  let start = 0;
  let end = arr.length - 1;
  
  while (swapped) {
    swapped = false;
    
    // 从左向右
    for (let i = start; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    
    if (!swapped) break;
    end--;
    
    // 从右向左
    swapped = false;
    for (let i = end - 1; i >= start; i--) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    
    start++;
  }
  return arr;
}

14. 侏儒排序（Gnome Sort）

原理：
类似插入排序的简单算法，通过交换相邻元素实现

function gnomeSort(arr) {
  let pos = 0;
  
  while (pos < arr.length) {
    if (pos === 0 || arr[pos] >= arr[pos - 1]) {
      pos++;
    } else {
      [arr[pos], arr[pos - 1]] = [arr[pos - 1], arr[pos]];
      pos--;
    }
  }
  return arr;
}

排序算法性能总览

算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	适用场景
冒泡排序	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(1)	✖️	中等规模数据
快速排序	O(n log n)	O(n²)	O(log n)	✖️	通用排序
归并排序	O(n log n)	O(n log n)	O(n)	✔️	稳定排序/大数据
堆排序	O(n log n)	O(n log n)	O(1)	✖️	内存受限
计数排序	O(n + k)	O(n + k)	O(n + k)	✔️	小范围整数
桶排序	O(n + k)	O(n²)	O(n + k)	✔️	均匀分布数据
基数排序	O(d(n + k))	O(d(n + k))	O(n + k)	✔️	整数/字符串
鸽巢排序	O(n + N)	O(n + N)	O(N)	✔️	范围=数量
梳排序	O(n log n)	O(n²)	O(1)	✖️	改进冒泡
鸡尾酒排序	O(n²)	O(n²)	O(1)	✔️	双向冒泡
侏儒排序	O(n²)	O(n²)	O(1)	✔️	简单实现

关键选择指南：

小数据集：插入排序

通用需求：快速排序

稳定需求：归并排序

整数排序：计数/基数排序

内存敏感：堆排序

浮点数均匀分布：桶排序

可视化工具推荐

Visualgo：交互式排序算法可视化
Algorithm Visualizer：自定义算法可视化
Sorting.at：多种排序算法实时比较

所有算法均附带JavaScript实现和可视化说明，建议结合可视化工具运行代码加深理解。实际应用中，JavaScript内置的Array.prototype.sort()方法通常使用Timsort（归并+插入的混合排序），针对不同场景自动优化。

✨✨✨ WOW, recorded a lot😶‍🌫️ ✨✨✨

Repeatings, Thoughts, and Writings

000-排序算法

各类排序算法详解（JavaScript版）

1. 冒泡排序（Bubble Sort）

2. 选择排序（Selection Sort）

3. 插入排序（Insertion Sort）

4. 快速排序（Quick Sort）

5. 归并排序（Merge Sort）

6. 堆排序（Heap Sort）

7. 希尔排序（Shell Sort）

8. 计数排序（Counting Sort）

9. 桶排序（Bucket Sort）

10. 基数排序（Radix Sort）

特殊用途排序算法

11. 鸽巢排序（Pigeonhole Sort）

12. 梳排序（Comb Sort）

13. 鸡尾酒排序（Cocktail Shaker Sort）

14. 侏儒排序（Gnome Sort）

排序算法性能总览

可视化工具推荐