快速排序 Quick-sort

算法

快速排序,Quick-Sort,典型的分治策略(divide and conquer)。因其平均性能很好,同时能进行原址排序,因而通常是实操时最好的选择。其核心思想是在序列中选取一个元素作为参考元,然后将待排序序列划分为小于和大于参考元的两个子序列,对子序列继续快速排序,直到子序列中有1或0个元素。等于参考元的元素,放在哪边都可以。

也就是说,序列data[left, right],会被拆分为子序列data[left, p-1], data[p+1, right],其中data[p]是参考元。满足data[left, p-1]的每个元素小于等于data[p],同时data[p] 小于等于 data[p+1, right] 中的每个元素。之后对两个子序列递归的快排。

该操作不需要合并,因为是在原址排序。

快排的关键步骤是确定参考元的索引位置 p,思路如图:

image-20200409205947789

索引 j 是需要比较的元素,从left到right-1。索引 i 是小于参考元的最后一个元素。每当找到一个小于参考元的元素,就将 i 右移,将小于参考元的元素交换过来,比较下一个。最后,i 的后边的元素于 right 元素交换,将参考元素移动到中间来。此时就将序列划分为两部分了。data[left, i-1] <= data[i], data[i] <= data[i+1, right]。

递归调用的过程,我们仅需要判断序列中是否还有2个或以上元素即可。

编码

go

// 快速排序
func QuickSort(data []int) {
	// 初始 左,右索引
	quickSort(data, 0, len(data)-1)
}
// 递归快排
func quickSort(data []int, left, right int) {
	// 存在 1 个以上的元素,做递归快排
	if left < right {
		// 确定分割索引
		p := partition(data, left, right)
		// 基于p,左右分别边快排
		quickSort(data, left, p-1)
		quickSort(data, p+1, right)
	}
}
// 确定分割点
func partition(data []int, left, right int) int {
	// 最后一个元素作为参考元
	v := data[right]
	// i 索引表示最后一个小于参考元的元素索引
	i := left-1
	// j 用于遍历全部元素与参考元进行比较
	for j:=left; j<=right-1; j++ {
		// 若数据小于参考元
		if data[j] < v {
			// 右移i
			i ++
			// 交换 i,j 元素值
			data[j], data[i] = data[i], data[j]
		}
	}
	// 后移i,指向第一个不小于参考元的元素
	i ++
	// 交换i和参考元的值
	data[i], data[right] = data[right], data[i]
	// 返回i,此时i就是参考元的索引
	return i
}

// 测试
data := []int{5, 3, 8, 1, 2, 7, 4, 0, 9, 6}
QuickSort(data)
fmt.Println(data) 
[0 1 2 3 4 5 6 7 8 9]

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

python

# 快速排序
def QuickSort(data):
  quickSort(data, 0, len(data)-1)

# 递归调用
def quickSort(data, left, right):
  # 元素数量大于1个
  if left < right :
    # 确定参考元索引
    p = partition(data, left, right)
    # 左右分别快排
    quickSort(data, left, p-1)
    quickSort(data, p+1, right)

# 确定参考元
def partition(data, left, right):
  # 最后元素为参考元
  v = data[right]
  # 初始化小于参考元索引 i
  i = left - 1
  # 遍历全部元素与参考元比较,不用包含参考元
  for j in range(left, right):
    # 若数据小于参考元
    if data[j] < v :
      # 右移 i
      i += 1
      # 交换 i,j 元素值
      data[i], data[j] = data[j], data[i]
  # 后移i,指向第一个不小于参考元的元素
  i += 1
  # 交换i和参考元的值
  data[i], data[right] = data[right], data[i]
  # 返回i,此时i就是参考元的索引
  return i

data = [5, 3, 8, 1, 2, 7, 4, 0, 9, 6]
QuickSort(data)
print(data) 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

JavaScript

function QuickSort(data) {
  quickSort(data, 0, data.length-1)
}

function quickSort(data, left, right) {
  if (left < right) {
    // 获取参考元素索引
    let p = partition(data, left, right)
    // 左右分别快排
    quickSort(data, left, p-1)
    quickSort(data, p+1, right)
  }

}

// 确定参考元素索引
function partition(data, left, right) {
  // 参考元
  let v = data[right]
  // 将全部小于参考元的元素左移
  let i = left - 1
  for (j=left; j<right; j++) {
    if (data[j] < v) {
      i++
      [data[i], data[j]] = [data[j], data[i]]
    }
  }
  // 交换 i++ 与 right 索引元素
  i++
  [data[i], data[right]] = [data[right], data[i]]
  return i
}

// 测试通过
data = [5, 3, 8, 1, 2, 7, 4, 0, 9, 6]
QuickSort(data)
console.log(data)
// Array(10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
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

PHP

to be contined
1

分析

算法的时间复杂度为O(nlgn)。但如果是最坏的情况,也就是每次参考元都是最大或最小的元素,那么划分的就很不平均,会导致速度变慢,最坏的情况可达 O(n^2)。

实操时,若数据规模较大,可以选择随机选择参考元的方案,来替代选择最后一个元素为参考元的方案,来提升划分的平衡性,提高性能。

随机选择的伪代码:

RANDOM-PARTITION (data, left, right)
	i = RANDOM(left to right)
	SWAP(data[i], data[right]) 
1
2
3

编码示例

// go
func randPartition(data []int, left, right int) int {
	// 随机索引
	rand.Seed(time.Now().UnixNano())
	randI := left + rand.Intn(right-left)
	// 交互随机元素和末尾元素
	data[right], data[randI] = data[randI], data[right]
	return partition(data, left, right)
}
1
2
3
4
5
6
7
8
9
# python
def randPartition(data, left, right):
  import random
  randI = random.randint(left, right)
  data[randI], data[right] = data[right], data[randI]
  return partition(data, left, right)
1
2
3
4
5
6
// JavaScript
function randPartition(data, left, right) {
    let randI = left + Math.ceil(Math.random()*(right-left))
    let t = data[right]
    data[right] = data[randI]
    data[randI] = t
    return partition(data, left, right) 
}
1
2
3
4
5
6
7
8
// PHP
1