前端-快速排序 (交换排序)

1. 算法思想:

   • 在待排序的表中L[0....n-1]中, 任意取一个元素作为基准值pivot, 通过一趟排序将待排序列划分为两个独立的部分, 其中L[0 ... k-1]和L[k+1 ... n-1]
   • 其中L[0 ... k-1]所有的元素都小于pivot基准元素, L[k+1 ... n-1]中的元素都大于或者等于pivot
   • 同时将pivot放在最终的位置L[k]上的这一趟过程称之为快速排序

2. 时间复杂度: O(n * log2n)

3. 稳定性: 不稳定

4. 优化:

   • 当递归过程中的子序列的规模较小的时, 不要再继续递归调用快速排序, 可以采用直接插入排序算法进行后续的操作
   • 尽量选取一个可以将数据中分的枢纽元素 (从序列中头尾以及中间选取三个元素, 将三个元素的中间值作为枢纽元素, 或者随机在序列中获取)

/* 时间复杂度: log2n*/
function QuickSort(arr, low, high) {
  if (low < high) {
    const pivotPos = PartionSort(arr, low, high);
    QuickSort(arr, low, pivotPos);
    QuickSort(arr, pivotPos + 1, high);
  }
}

/* 时间复杂度: n */
// 一次PartionSort之后 将arr[low]放在了合适的位置上, 其左侧都比其小, 右侧都比其大
function PartionSort(arr, low, high) {
  // 将当前表中的第一个元素当做枢纽值
  const pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= pivot) high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

/*
    随机选择基准值pivot
*/
function PartionSort2(arr, low, high) {
  const randIndex = low + Math.floor(Math.random() * (high - low + 1));
  // 将随机索引处的值 切换到第一个的位置
  Swap(arr, randIndex, low);
  // 置当前表中的第一个元素为基准元素
  const pivot = arr[low];
  let i = low;
  // 从第二个元素开始, 将比pivot小的元素  移动到pivot的前面即可
  for (let j = low + 1; j <= high; j++) {
    if (arr[j] < pivot) {
      Swap(arr, ++i, j);
    }
  }
  Swap(arr, i, low);
  return i;
}

function Swap(arr, low, high) {
  const temp = arr[low];
  arr[low] = arr[high];
  arr[high] = temp;
  return arr;
}

const a = [5, 2, 4, 3, 8, 6, 9, 0, 1, 7];
QuickSort(a, 0, a.length - 1);
console.log(a);