快速排序

发表于 | 分类于

快速排序为 O(nlogn) 时间复杂度的算法，是一种不稳定的算法，最坏的情况下会退化成 O(n^2) 的时间复杂度。快速排序其实类似于二叉树的前序遍历。

方法一

算法思路，假设需要排序的数组为： “6 1 2 7 9 3 4 5 10 8”：

  1. 分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”
  2. 先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换它们
  3. 这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。当 i 与 j 相遇的时候，将准基数 6 和 相遇点索引交换（这里是3），交换之后序列如下：“3 1 2 5 4 6 9 7 10 8”，6 左边的数都小于等于 6，6右边的数都大于等于 6
  4. 之后再以 6 为分界点，拆成 2 个序列，继续重复上面的操作，直到不可拆分出新的子序列为止，数组就变成有序的了

代码如下：

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
function quickSortOne(arr, left, right) {
  if (left > right) {
  	return
  }
  let temp = arr[left]
  let i = left, j = right
  while (i !== j) {
  	while (arr[j] >= temp && i < j) { // 顺序很重要，要先从右往左找
      j--
    }
    while (arr[i] <= temp && i < j) { // 再从左往右找
      i++
    }
    if (i < j) { // 说明两者还未相遇，交换位置
      let t = arr[i]
      arr[i] = arr[j]
      arr[j] = t
    }
  }
  arr[left] = arr[i]
  arr[i] = temp
  quickSortOne(arr, left, i-1) // 继续处理左边的
  quickSortOne(arr, i+1, right) // 继续处理右边的
}
let testArr = [5,1,6,4,3,8,2,7,10,9]
quickSortOne(testArr, 0, 9)
console.log(testArr) // 1 2 3 4 5 9 7 8 9 10

方法二

算法思路：

  1. 每次在当前需要排序的数组选择一个元素，以这个元素为基点，例如 “4 6 2 3 1 5 7 8” 这个数组，选择 4 作为基点
  2. 之后想办法把 4 这个元素挪到一个位置，使 4 之前的位置都小于 4 ，4 之后的所有元素都是大于 4 的
  3. 之后我们要做的事情，是对小于 4 的这部分字数组和大于 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 对arr[l...r]范围内的数组进行插入排序
function insertSort(arr, l, r){
  for (let i = l+1; i <= r; i++) {
    let e = arr[i]
	let j
    for (j = i; j > l && arr[j-1] > e; j--) {
      arr[j] = arr[j-1]
    }
    arr[j] = e
  }
}

// 对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
function __partition(arr, l, r) {

  // 待优化：数据量大，可以取 a[l]到a[r]之间的随机数为基点
  // swap(arr[l],arr[random()%(r-l+1)+l])
  // let tempOne = arr[l]
  // arr[l] = arr[rand()%(r-l+1)+l]
  // arr[rand()%(r-l+1)+l] = tempOne

  let v = arr[l] // v为基点
  // arr[l+1...j] < v; arr[j+1...i] > v
  let j = l
  for (let i = l + 1; i <= r; i++) {
	// 当 arr[i] > v 的时候什么都不需要做，i++ 就行
    if (arr[i] < v) {
      // swap(arr[j+1], arr[i])
      let temp = arr[j+1]
      arr[j+1] = arr[i]
      arr[i] = temp
      j++
    }
  }
  // swap(arr[l],arr[j])
  let tempTwo = arr[l]
  arr[l] = arr[j]
  arr[j] = tempTwo
  return j
}

// 对 arr[l...r]部分进行快速排序
function __quickSort(arr, l, r) {
  if (l >= r) {
    return
  }
  // if (r - l <= 15) { // 优化，当数组范围小于15位采用插入排序
  // 	insertSort(arr, l, r)
  // 	return;
  // }

  let p = __partition(arr, l , r)
  __quickSort(arr, l , p - 1)
  __quickSort(arr, p + 1, r)
}

function quickSort(arr, n) {
  __quickSort(arr, 0, n - 1)
}
let arr = [50,30,10,40,60,80,70,100,20,90]
quickSort(arr, 10)
console.log(arr)

方法三

对于上面第一种和第二种方法，对于有大量重复健值的数组排序，很容易使数组退化成 O(n^2) 复杂度的算法，对于此，我们可以用另外一种快速排序方法，也就是：三路快排（Quick Sort 3 Ways）。

算法思想：

之前的排序方法都是把数组分成 2 部分，小于基数 v 和大于基数 v,而三路快排则是把数组分为三部分：小于 v, 等于 v 和 大于 v。这样我们在对比的过程种，对于等于 v 的部分就不需要操作，只需要操作小于和大于 v 的数值。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 三路快速排序处理 arr[l...r]
// arr[l...r] 分为 <v ; ==v ; >v 三部分
// 之后递归对 <v ; >v 两部分进行三路快速排序
function __quickSort3Ways(arr, l, r) {
  if (l >= r) {
    	return;
  }
  // if (r - l <= 15) { // 优化，当数组范围小于15位采用插入排序
  //     insertSort(arr, l, r);
  //     return;
  // }

  // partition
  // 优化取 a[l]到a[r]之间的随机数
  // swap(arr[l],arr[random()%(r-l+1)+l]);
  // let tempOne = arr[l];
  // arr[l] = arr[rand()%(r-l+1)+l];
  // arr[rand()%(r-l+1)+l] = tempOne;

  let v = arr[l];

  let lt = l; // arr[l+1...lt] < v
  let gt = r + 1; // arr[gt...r] > v
  let i = l + 1; // arr[lt+1...i) == v
  while(i < gt) {
    if (arr[i] < v) {
        // swap(arr[i], arr[lt + 1]);
        let tempTwo = arr[i];
        arr[i] = arr[lt + 1];
        arr[lt + 1] = tempTwo;
        lt++;
        i++;
    } else if (arr[i] > v) {
        // swap(arr[i], arr[gt - 1]);
        let tempThree = arr[i];
        arr[i] = arr[gt - 1];
        arr[gt - 1] = tempThree;
        gt--;
    } else {
        i++;
    }
  }
  // swap(arr[l],arr[lt]);
  let tempFour = arr[l];
  arr[l] = arr[lt];
  arr[lt] = tempFour;

  __quickSort3Ways(arr, l, lt - 1);
  __quickSort3Ways(arr, gt, r);
}

function quickSort3Ways(arr, n) {
  __quickSort3Ways(arr, 0, n - 1);
}

let testArr2 = [5,1,6,4,3,8,2,7,10,9,18,15,12,16]
quickSort3Ways(testArr2, 14)
console.log(testArr2)