0%

《数据结构与算法》快速排序

快速排序例子

举一个例子:5 9 1 6 8 14 6 49 25 4 6 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
一般取第一个数 5 作为基准,从它左边和最后一个数使用[]进行标志,

如果左边的数比基准数大,那么该数要往右边扔,也就是两个[]数交换,这样大于它的数就在右边了,然后右边[]数左移,否则左边[]数右移。

5 [9] 1 6 8 14 6 49 25 4 6 [3] 因为 9 > 5,两个[]交换位置后,右边[]左移
5 [3] 1 6 8 14 6 49 25 4 [6] 9 因为 3 !> 5,两个[]不需要交换,左边[]右移
5 3 [1] 6 8 14 6 49 25 4 [6] 9 因为 1 !> 5,两个[]不需要交换,左边[]右移
5 3 1 [6] 8 14 6 49 25 4 [6] 9 因为 6 > 5,两个[]交换位置后,右边[]左移
5 3 1 [6] 8 14 6 49 25 [4] 6 9 因为 6 > 5,两个[]交换位置后,右边[]左移
5 3 1 [4] 8 14 6 49 [25] 6 6 9 因为 4 !> 5,两个[]不需要交换,左边[]右移
5 3 1 4 [8] 14 6 49 [25] 6 6 9 因为 8 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [25] 14 6 [49] 8 6 6 9 因为 25 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [49] 14 [6] 25 8 6 6 9 因为 49 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [6] [14] 49 25 8 6 6 9 因为 6 > 5,两个[]交换位置后,右边[]左移
5 3 1 4 [14] 6 49 25 8 6 6 9 两个[]已经汇总,因为 14 > 5,所以 5 和[]之前的数 4 交换位置
第一轮切分结果:4 3 1 5 14 6 49 25 8 6 6 9

现在第一轮快速排序已经将数列分成两个部分:

4 3 1 和 14 6 49 25 8 6 6 9

左边的数列都小于 5,右边的数列都大于 5。

使用递归分别对两个数列进行快速排序。

Golang实现

在数组元素少的情况下,可以使用插入排序来优化,下面看实现

golang实现:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package main

import (
"fmt"
)


// 普通快速排序
func QuickSort(array []int, begin, end int) {
if begin < end {
// 当数组小于 4 时使用直接插入排序
if end-begin <= 4 {
insertSort(array[begin : end+1])
return
}

// 进行切分
loc := partition(array, begin, end)
// 对左部分进行快排
QuickSort(array, begin, loc-1)
// 对右部分进行快排
QuickSort(array, loc+1, end)
}
}

func insertSort(values []int) {
length := len(values)
if length <= 1 {
return
}

for i := 1; i < length; i++ {
tmp := values[i] // 从第二个数开始,从左向右依次取数
key := i - 1 // 下标从0开始,依次从左向右

// 每次取到的数都跟左侧的数做比较,如果左侧的数比取的数大,就将左侧的数右移一位,直至左侧没有数字比取的数大为止
for key >= 0 && tmp < values[key] {
values[key+1] = values[key]
key--
//fmt.Println(values)
}

// 将取到的数插入到不小于左侧数的位置
if key+1 != i {
values[key+1] = tmp
}
}
}

// 切分函数,并返回切分元素的下标
func partition(array []int, begin, end int) int {
i := begin + 1 // 将array[begin]作为基准数,因此从array[begin+1]开始与基准数比较!
j := end // array[end]是数组的最后一位

// 没重合之前
for i < j {
if array[i] > array[begin] {
array[i], array[j] = array[j], array[i] // 交换
j--
} else {
i++
}
}

/* 跳出while循环后,i = j。
* 此时数组被分割成两个部分 --> array[begin+1] ~ array[i-1] < array[begin]
* --> array[i+1] ~ array[end] > array[begin]
* 这个时候将数组array分成两个部分,再将array[i]与array[begin]进行比较,决定array[i]的位置。
* 最后将array[i]与array[begin]交换,进行两个分割部分的排序!以此类推,直到最后i = j不满足条件就退出!
*/
if array[i] >= array[begin] { // 这里必须要取等“>=”,否则数组元素由相同的值组成时,会出现错误!
i--
}

array[begin], array[i] = array[i], array[begin]
return i
}

func main() {
a := []int{2, 45, 1, 78}
QuickSort(a, 0, len(a) - 1)
fmt.Println(a) // 输出int值
}

参考出处:https://zhuanlan.zhihu.com/p/119079995




微信关注我,及时接收最新技术文章