快速排序 - x-note

Search…
快速排序
快速排序（Quick Sort）又称为划分交换排序（partition-exchange sort）是一种有效率的排序算法。
平均时间复杂度：O(nlog⁡2n)O({n}\log_{2}{n})O(nlog2​n)
​
最好时间复杂度：O(nlog⁡2n)O({n}\log_{2}{n})O(nlog2​n)
​
最坏时间复杂度：O(n2)O(n^2)O(n2)
​
空间复杂度：根据实现方式不同为 O(n)O(n)O(n)
 或 O(log⁡2n)O(\log_{2}{n})O(log2​n)
​
稳定性：不稳定
排序方式：原地（In-place）
步骤：
1.从序列中挑出一个元素作为基准（Pivot），一般选取序列中的第一个；
2.从后向前遍历剩余元素，找到第一个比基准小的元素的索引；
3.从前向后遍历剩余元素，找到第一个比基准数大的元素的索引；
4.交换两个元素；
5.重复 2~4，直到从后向前的游标和从前向后的游标重叠；
6.交换基准与当前两个游标重叠的位置的元素，此时，所有比基准值小的元素放在基准前面，所有比基准大的放在基准后面（相同的可放在前面或后面）；
7.划分结束后，以基准所在位置划分左右两个分区；
8.对新划分的分区执行 1~5，直到无法划分分区。
可以简单理解为，从每个的分区中，取一个基准值，然后找到这个基准值所在的位置。
递归实现：
function swap(arr, i, j) {
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}
​
function quickSort(arr, left, right) {
  const len = arr.length;
  if (left > right) {
    return arr;
  }
  let pivot = arr[left];
  let i = left;
  let j = right;
  while (i != j) {
    while (arr[j] >= pivot && i < j) {
      j--;
    }
    while (arr[i] <= pivot && i < j) {
      i++;
    }
    if (i < j && arr[i] !== arr[j]) {
      swap(arr, i, j);
    }
  }
​
  if (left !== i && arr[left] !== arr[i]) {
    swap(arr, left, i);
  }
​
  quickSort(arr, left, i - 1);
  quickSort(arr, i + 1, right);
​
  return arr;
}
​
let arr = [3, 7, 8, 5, 2, 1, 9, 5, 4];
quickSort(arr, 0, arr.length - 1); // [1, 2, 3, 4, 5, 5, 7, 8, 9]
非递归实现：
function swap(arr, i, j) {
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}
const quickSort = (arr) => {
  const stack = [0, arr.length - 1];
​
  while (stack.length > 0) {
    const left = stack.pop();
    const right = stack.pop();
​
    if (left >= right) {
      continue;
    }
​
    let i = left;
    let j = right;
    let p = arr[left];
    while (i < j) {
      while (i < j && arr[j] >= p) {
        j--;
      }
      while (i < j && arr[i] <= p) {
        i++;
      }
      if (i !== j && arr[i] !== arr[j]) {
        swap(arr, i, j);
      }
    }
    stack.push(left, i - 1);
    stack.push(i + 1, right);
  }
  return arr;
};
​
let arr = [3, 7, 8, 5, 2, 1, 9, 5, 4];
quickSort(arr, 0, arr.length - 1); // [1, 2, 3, 4, 5, 5, 7, 8, 9]
选择排序
归并排序
Last modified 2yr ago
Copy link