Chrome的[].sort就是使用的改进过的快排, 之前没有作过多了解, 今天就来记录下

更新

[2019-4-14]

  • Initial Release

[2019-10-29]

Added

  • 新增原地算法实现

记录

时间复杂度

O(nlogn)

空间复杂度

O(1)

思路

思路一

Out-Place

  • 定义基准middleIndex、middle
  • 两个数组空间
    • left保存比middle小的数
    • right保存比middle大的数
  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort(nums) {
  if(nums.length <= 1) {
    return nums;
  }

  const [left, right] = [[], []];
  const middleIndex = ~~(nums.length / 2);
  const middle = (nums.splice(middleIndex, 1))[0];

  for(let i = 0; i < nums.length; i++) {
    nums[i] < middle
      ? (left.push(nums[i]))
      : (right.push(nums[i]))
  }

  return quickSort(left).concat([middle], quickSort(right));
}

思路二

In-Place

  1. 选取基准值
  2. 右指针查找第一个小于基准值的数, 与左指针交换
  3. 左指针查找第一个大于基准值的数, 与右指针交换
  4. 两指针相遇, 基准值归位
  5. 对于以基准值拆分的两块数组, 分别进行递归(1, 2, 3, 4)操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function quickSort(originArr) {
  _aidedQuickSort(originArr, 0, originArr.length - 1);
}

function _aidedQuickSort(arr, left, right) {
  if (arr.length <= 1 || left >= right) {
    return;
  }

  const baseValue = arr[left];
  let leftIndex = left;
  let rightIndex = right;

  while (leftIndex < rightIndex) {
    // 右指针查找第一个小于基准值的数
    while (leftIndex < rightIndex && arr[rightIndex] >= baseValue) {
      rightIndex--;
    }
    // 交换值
    arr[leftIndex] = arr[rightIndex];

    // 左指针查找第一个大于基准值的数
    while (leftIndex < rightIndex && arr[leftIndex] <= baseValue) {
      leftIndex++;
    }
    // 交换值
    arr[rightIndex] = arr[leftIndex];
  }

  // 左右指针相遇, 基准值归位
  arr[leftIndex] = baseValue;

  _aidedQuickSort(arr, left, leftIndex - 1);
  _aidedQuickSort(arr, leftIndex + 1, right);
}