码海

# 快速排序

# 算法原理

快速排序是一种高效的排序算法，采用分治策略。其基本思想是：选择一个基准元素（pivot），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。

# 算法步骤

  1. 从数列中挑出一个元素作为基准（pivot）
  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）
  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

# 动图演示

比较次数: 0

交换次数: 0

# 代码实现

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left - 1;
  
  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

# 复杂度分析

# 时间复杂度

  • 最好情况：O(n log n)，每次都能平均分割
  • 最坏情况：O(n²)，当数组已经有序或逆序时
  • 平均情况：O(n log n)

# 空间复杂度

  • O(log n)，递归调用栈的深度

# 算法特点

# 优点

  • 平均情况下效率高
  • 原地排序，不需要额外的数组空间
  • 缓存友好，数据访问局部性好

# 缺点

  • 不稳定排序
  • 在最坏情况下性能较差
  • 对于小规模数据，可能不如插入排序

# 适用场景

  • 大规模数据排序
  • 对稳定性不敏感的场景
  • 平均性能要求较高的场景

# 优化方案

  1. 三数取中法选择基准值：避免最坏情况
  2. 小规模数据使用插入排序
  3. 处理重复元素：三向切分快速排序
function optimizedQuickSort(arr) {
  const INSERTION_SORT_THRESHOLD = 10;
  
  function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
      const current = arr[i];
      let j = i - 1;
      
      while (j >= left && arr[j] > current) {
        arr[j + 1] = arr[j];
        j--;
      }
      
      arr[j + 1] = current;
    }
    return arr;
  }
  
  function medianOfThree(arr, left, right) {
    const mid = Math.floor((left + right) / 2);
    
    // 对左中右三个元素排序
    if (arr[left] > arr[mid]) {
      [arr[left], arr[mid]] = [arr[mid], arr[left]];
    }
    if (arr[left] > arr[right]) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
    }
    if (arr[mid] > arr[right]) {
      [arr[mid], arr[right]] = [arr[right], arr[mid]];
    }
    
    // 将中间值放到倒数第二个位置
    [arr[mid], arr[right - 1]] = [arr[right - 1], arr[mid]];
    return arr[right - 1];
  }
  
  function quickSort(arr, left, right) {
    // 小规模数组使用插入排序
    if (right - left <= INSERTION_SORT_THRESHOLD) {
      return insertionSort(arr, left, right);
    }
    
    // 三数取中选择基准值
    const pivot = medianOfThree(arr, left, right);
    
    // 分区
    let i = left;
    let j = right - 1;
    
    while (true) {
      while (arr[++i] < pivot) {}
      while (arr[--j] > pivot) {}
      
      if (i < j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      } else {
        break;
      }
    }
    
    // 将基准值放到正确位置
    [arr[i], arr[right - 1]] = [arr[right - 1], arr[i]];
    
    // 递归排序子数组
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
    
    return arr;
  }
  
  return quickSort(arr, 0, arr.length - 1);
}

← 动态规划基础 →