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

更新


[2019-4-14]

  • Initial Release

[2019-10-29]

Added

  • 新增原地算法实现

记录


时间复杂度

O(nlogn)

空间复杂度

O(1)

思路


思路一

Out-Place

  • 定义基准middleIndexmiddle
  • 两个数组空间
    • 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);
}