1. 算法概述

排序算法可以分为两大类：

• 比较类排序：通过比较元素间的大小来决定次序
• 非比较类排序：不通过比较来决定元素间的相对次序

下面是常见排序算法的时间复杂度对比：

排序算法	平均时间复杂度	最佳情况	最差情况	空间复杂度	排序方式	稳定性
冒泡排序	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 log² n)	O(1)	原地排序	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	非原地排序	稳定
快速排序	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(1)	原地排序	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	非原地排序	稳定
桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)	非原地排序	稳定
基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	非原地排序	稳定

2. 比较类排序算法

2.1 冒泡排序 (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;
}

// 使用示例
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("冒泡排序结果:", bubbleSort([...arr]));

适用场景：教学示例或小规模数据排序，实际应用中较少使用。

2.2 选择排序 (Selection Sort)

原理：每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。

function selectionSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    // 假设当前索引i的元素是最小的
    let minIndex = i;
    
    // 在未排序部分寻找最小元素
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // 将找到的最小元素与第i个元素交换
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

// 使用示例
console.log("选择排序结果:", selectionSort([...arr]));

适用场景：数据量小且交换成本高的场景。

2.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--;
    }
    
    // 插入current到正确位置
    arr[j + 1] = current;
  }
  
  return arr;
}

// 使用示例
console.log("插入排序结果:", insertionSort([...arr]));

适用场景：小规模数据或基本有序的数据集。

2.4 希尔排序 (Shell Sort)

原理：是插入排序的改进版，通过将原始列表分割成多个子列表来进行插入排序。

function shellSort(arr) {
  const n = arr.length;
  let gap = Math.floor(n / 2);
  
  while (gap > 0) {
    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;
    }
    
    gap = Math.floor(gap / 2);
  }
  
  return arr;
}

// 使用示例
console.log("希尔排序结果:", shellSort([...arr]));

适用场景：中等规模的数据集，是插入排序的高效改进版。

2.5 归并排序 (Merge Sort)

原理：采用分治法，将列表分成两半，分别排序，然后合并结果。

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  // 分割数组
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // 递归排序并合并
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  // 比较两个数组的元素，按顺序合并
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // 将剩余元素添加到结果数组
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 使用示例
console.log("归并排序结果:", mergeSort([...arr]));

适用场景：需要稳定排序且对空间复杂度要求不高的场景，尤其适合链表排序。

2.6 快速排序 (Quick Sort)

原理：选择一个基准元素，将数组分成两部分，一部分小于基准，一部分大于基准，然后递归地对这两部分进行排序。

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // 分区操作，返回基准元素的正确位置
    const pivotIndex = partition(arr, low, high);
    
    // 递归排序基准左右两边的子数组
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  
  return arr;
}

function partition(arr, low, high) {
  // 选择最后一个元素作为基准
  const pivot = arr[high];
  let i = low - 1; // 小于基准的元素的索引
  
  for (let j = low; j < high; j++) {
    // 如果当前元素小于或等于基准
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  // 将基准元素放到正确位置
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// 使用示例
console.log("快速排序结果:", quickSort([...arr]));

适用场景：大规模数据集的通用排序算法，是许多编程语言内置排序函数的基础。

2.7 堆排序 (Heap Sort)

原理：利用堆这种数据结构所设计的一种排序算法。

function heapSort(arr) {
  const n = arr.length;
  
  // 构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  
  // 一个个从堆顶取出元素
  for (let i = n - 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);
  }
}

// 使用示例
console.log("堆排序结果:", heapSort([...arr]));

适用场景：需要原地排序且最坏情况下仍能保持O(n log n)时间复杂度的场景。

3. 非比较类排序算法

3.1 计数排序 (Counting Sort)

原理：使用一个额外的数组来计数每个元素出现的次数，然后根据计数信息重构排序后的数组。

function countingSort(arr) {
  const n = arr.length;
  
  // 找出数组中的最大值
  const max = Math.max(...arr);
  
  // 创建计数数组并初始化为0
  const count = new Array(max + 1).fill(0);
  
  // 计算每个元素的出现次数
  for (let i = 0; i < n; i++) {
    count[arr[i]]++;
  }
  
  // 修改计数数组，使每个元素表示小于等于其索引的元素个数
  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }
  
  // 创建输出数组
  const output = new Array(n);
  
  // 构建输出数组
  for (let i = n - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }
  
  return output;
}

// 使用示例
const countingArr = [4, 2, 2, 8, 3, 3, 1];
console.log("计数排序结果:", countingSort([...countingArr]));

适用场景：整数排序且数据范围不大(k不大)的情况。

3.2 桶排序 (Bucket Sort)

原理：将数组分到有限数量的桶里，每个桶再分别排序。

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) {
    return arr;
  }
  
  // 找出最小值和最大值
  let minValue = arr[0];
  let maxValue = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }
  
  // 初始化桶
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  
  // 将数据分配到各个桶中
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }
  
  // 对每个桶进行排序，并合并结果
  const sortedArray = [];
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] != null) {
      insertionSort(buckets[i]); // 使用插入排序对每个桶排序
      sortedArray.push(...buckets[i]);
    }
  }
  
  return sortedArray;
}

// 使用示例
const bucketArr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51];
console.log("桶排序结果:", bucketSort([...bucketArr]));

适用场景：数据均匀分布在某个范围内且易于划分桶的情况。

3.3 基数排序 (Radix Sort)

原理：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

function radixSort(arr) {
  // 找出最大值以确定位数
  const max = Math.max(...arr);
  
  // 从个位开始，对每一位进行计数排序
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
  }
  
  return arr;
}

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);
  
  // 计算每个数字的出现次数
  for (let i = 0; i < n; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }
  
  // 修改计数数组
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  // 构建输出数组
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  
  // 将输出数组复制回原数组
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

// 使用示例
const radixArr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("基数排序结果:", radixSort([...radixArr]));

适用场景：整数或字符串排序，特别是当数据的位数或长度固定时。

4. 性能对比与选择指南

4.1 算法选择建议

1. 小规模数据(n ≤ 10)：插入排序简单高效
2. 中等规模数据(10 < n ≤ 1000)：希尔排序或快速排序
3. 大规模数据(n > 1000)：
   • 一般情况：快速排序(平均性能最好)
   • 需要稳定排序：归并排序
   • 担心最坏情况：堆排序
4. 特定类型数据：
   • 整数且范围小：计数排序
   • 数据均匀分布：桶排序
   • 多位整数或字符串：基数排序

4.2 JavaScript内置排序

JavaScript的Array.prototype.sort()方法通常使用Timsort算法(一种混合排序算法，结合了归并排序和插入排序的优点)：

// 默认按字符串Unicode码点排序
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
arr.sort(); // [1, 1, 2, 3, 4, 5, 6, 9]

// 使用比较函数进行数字排序
arr.sort((a, b) => a - b); // 升序
arr.sort((a, b) => b - a); // 降序

5. 总结

排序算法是计算机科学的基础，不同的排序算法有各自适用的场景。理解它们的原理和特性有助于在实际开发中选择最合适的算法。对于大多数应用场景，JavaScript内置的sort()方法已经足够高效，但在特定场景下，自定义实现特定算法可能会获得更好的性能。