经典快速排序

思路:选取数组中的第1个元素作为划分元素,划分为两部分,左边一部分比该元素小,右边一部分比该元素大

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
package quickSortV1

import (
"InterviewQuestions/Algo/sort"
"fmt"
)

/**
* @Author: yirufeng
* @Email: yirufeng@foxmail.com
* @Date: 2020/9/10 7:45 上午
* @Desc:
*/

/*
快速排序第1个版本:选择第1个元素作为划分枢轴
注意:切片作为参数传递的时候是一个引用
*/
func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
var pivotkey int
if low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
quickSort(nums, pivotkey+1, high)
}
}

func partition(nums []int, low int, high int) int {
//选择划分元素
dummy := nums[low]
for low < high {
for low < high && dummy <= nums[high] {
high--
}
swap(nums, low, high)
for low < high && dummy > nums[low] {
low++
}
swap(nums, low, high)
}
//最后low == high
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}


//------------------------------for test------------------------------
func main() {

fmt.Println(QuickSort(sort.RandArray(100)))
}

经典快速排序的不足

虽然经典快速排序性能相对其他排序性能较高,但仍然有一定的瓶颈,例如如果是一个有序的数组。

此外快速排序可以从以下几点进行改进:

  1. 优化选取枢轴的策略
    1. 随机从low到high中选择一个下标对应的元素作为枢轴
    2. (三数取中)从left, high 以及mid对应的下标的元素中的三个选择一个大小居中的元素
    3. (九数取中)
  2. 优化不必要的交换:采用置换而不是交换。我们可以提前存储nums[low],之后每次在右边找到小的元素就将其赋值给nums[low],每次在左边找到大的元素可以直接赋值给nums[high]
  3. 优化小数组的排序方案:虽然快速排序可以有很好的性能,但是在数组较小时,直接插入排序效率比快速排序效率高(直接插入排序是简单排序中性能最好的)
  4. 对快排进行尾递归优化:如果传入一个大量数据且有序的数组,快排会不断的递归,栈的深度也会越来越深,因此很容易在数据量大且数据有序的时候造成栈溢出(申请不到更多的栈空间)

9QFpxr

优化方案1:随机选取一个元素作为枢轴

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
package quickSortV2

import (
"InterviewQuestions/Algo/sort"
"fmt"
"math/rand"
"time"
)

/**
* @Author: yirufeng
* @Email: yirufeng@foxmail.com
* @Date: 2020/9/10 8:06 上午
* @Desc: 随机选取一个元素作为枢轴
*/

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
var pivotkey int
if low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
quickSort(nums, pivotkey+1, high)

}
}

func partition(nums []int, low int, high int) int {
//设置随机数种子
rand.Seed(time.Now().UnixNano())
//选择[0,n)
//rand.Intn(n)
//选择划分元素
dummyIndex := rand.Intn(high-low+1) + low
swap(nums, low, dummyIndex)
temp := nums[low]
for low < high {
for low < high && temp <= nums[high] {
high--
}
swap(nums, low, high)
for low < high && temp >= nums[low] {
low++
}
swap(nums, low, high)
}
//最后low == high
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func main() {
fmt.Println(sort.RandArray(5))
fmt.Println(QuickSort(sort.RandArray(100)))
fmt.Println(QuickSort(sort.RandArray(5)))
}

优化方案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
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
package quickSortV3

import (
"InterviewQuestions/Algo/sort"
"fmt"
)

/**
* @Author: yirufeng
* @Email: yirufeng@foxmail.com
* @Date: 2020/9/10 8:06 上午
* @Desc: 元素进行置换而不是交换,从而优化不必要的交换
每次右边有小的时将该元素放置到low位置上,因为之前low位置我们就已经使用另外一个变量保存了
每次左边有大的元素的时候直接将该元素放置到high位置上,因为此时high位置上的元素已经被放置到了low左边的元素了
*/

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
var pivotkey int
if low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
quickSort(nums, pivotkey+1, high)
}
}

func partition(nums []int, low int, high int) int {
//选择划分元素
//关键点1
dummy := nums[low]

for low < high {
for low < high && dummy <= nums[high] {
high--
}
//第一次遍历到这里的时候由于我们提前存了low位置的元素,所以我们可以直接将high位置的值替换过来
//关键点2
nums[low] = nums[high]
for low < high && dummy >= nums[low] {
low++
}
//关键点3
nums[high] = nums[low]
}
//最后low == high,但此时需要将我们之前存的dummy替换到这个位置,这样数组才可以复原
//关键点4,最后记得还原
nums[low] = dummy
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func main() {
fmt.Println(QuickSort(sort.RandArray(30)))
}

优化方案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
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
package main

import (
"InterviewQuestions/Algo/sort"
insertSort "InterviewQuestions/templates/InsertSort"
"fmt"
)

/**
* @Author: yirufeng
* @Email: yirufeng@foxmail.com
* @Date: 2020/9/10 8:06 上午
* @Desc: 根据数组的大小优化排序方案,
因为直接插入排序是简单选择排序中性能最好的排序,所以当数据长度小于一个固定值我们使用直接插入排序,
*/


//设置元素个数到达多少的时候开始快速排序
const (
lengthQuickSort = 100
)

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
if len(nums) <= lengthQuickSort {
insertSort.InsertSortV2(nums)
} else {
var pivotkey int
if low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
quickSort(nums, pivotkey+1, high)
}
}
}

func partition(nums []int, low int, high int) int {

dummy := nums[low]

for low < high {
for low < high && dummy <= nums[high] {
high--
}
swap(nums, low, high)
for low < high && dummy >= nums[low] {
low++
}
swap(nums, low, high)
}
//最后low == high
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func main() {
for i := 0; i < 100; i++ {

}
fmt.Println(QuickSort(sort.RandArray(20)))
fmt.Println(QuickSort(sort.RandArray(200)))
}

优化方案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
package quickSortV5

import (
"InterviewQuestions/Algo/sort"
"fmt"
)

/**
* @Author: yirufeng
* @Email: yirufeng@foxmail.com
* @Date: 2020/9/10 8:06 上午
* @Desc: 尾递归进行优化
*/

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
var pivotkey int
// 尾递归优化关键点1:
for low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
//尾递归优化关键点2:
low = pivotkey + 1
}
}

func partition(nums []int, low int, high int) int {

//选择划分元素
dummy := nums[low]

for low < high {
for low < high && dummy <= nums[high] {
high--
}
swap(nums, low, high)
for low < high && dummy > nums[low] {
low++
}
swap(nums, low, high)
}
//最后low == high
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func main() {
fmt.Println(QuickSort([]int{4, 3, 2, 1}))
fmt.Println(QuickSort(sort.RandArray(100)))
}

优化方案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
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
84
85
package quickSortV6
//package main
import (
"InterviewQuestions/Algo/sort"
insertSort "InterviewQuestions/templates/InsertSort"
"fmt"
"math/rand"
"time"
)

/**
* @Author: yirufeng
* @Email: yirufeng@foxmail.com
* @Date: 2020/9/10 8:06 上午
* @Desc: 快速排序的终极版本
随机选择划分元素 + 尾递归优化 + 根据自己定义的大小自动选择插入排序或(使用替换而不是交换的带尾递归优化的随机快速排序)
*/

//优化4:设置一个边界用来标志什么时候使用快速排序什么时候使用直接插入排序
//设置元素个数到达多少的时候开始快速排序
const (
lengthQuickSort = 100
)

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
if len(nums) <= lengthQuickSort {
insertSort.InsertSortV2(nums)

} else {
var pivotkey int
//优化1:尾递归优化
for low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
low = pivotkey + 1
}
}

}

func partition(nums []int, low int, high int) int {
//优化2:使用随机数选择划分枢轴
//设置随机数种子
rand.Seed(time.Now().UnixNano())
//选择[0,n)
//rand.Intn(n)
//选择划分元素
dummyIndex := rand.Intn(high-low+1) + low
//将随机选择的元素放置到low位置上,以后便于在高处找到比划分元素小的时候我们可以直接让high赋值给low
swap(nums, low, dummyIndex)
dummyVal := nums[low]
for low < high {
for low < high && dummyVal <= nums[high] {
high--
}
//优化3:我们使用替换而不是交换
//高处找到小的直接赋值给low
nums[low] = nums[high]
for low < high && dummyVal >= nums[low] {
low++
}
//低处找到大的直接赋值给high
nums[high] = nums[low]
}
//最后low == high
nums[low] = dummyVal
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func main() {
fmt.Println(QuickSort([]int{4, 3, 2, 1}))
fmt.Println(QuickSort(sort.RandArray(20)))
fmt.Println(QuickSort(sort.RandArray(200)))
}

【左神代码优化】优化方案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
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func QuickSort(nums []int) {
quickSort(nums, 0, len(nums)-1)
}

func quickSort(nums []int, l, r int) {
if l < r {
//如果这里加上一步:将随机选中的一个元素与最后一个元素交换就是我们的随机快排
l1, r1 := partition(nums, l, r)
quickSort(nums, l, l1-1)
quickSort(nums, r1+1, len(nums)-1)
}

}

//使用nums[R]作为划分
func partition(nums []int, L, R int) (int, int) {
//最开始没有小于等于范围没有数字,
lessIndex := L - 1
largerIndex := R
num := nums[R]
cur := L
for cur < largerIndex {
if nums[cur] < num {
nums[lessIndex+1], nums[cur] = nums[cur], nums[lessIndex+1]
lessIndex++
cur++
} else if nums[cur] > num {
nums[largerIndex-1], nums[cur] = nums[cur], nums[largerIndex-1]
largerIndex--
} else if nums[cur] == num {
cur++
}
}
//因为我们最后一个是没有排序的,所以大于的索引位置处与最后一个位置的元素交换即可
nums[largerIndex], nums[R] = nums[R], nums[largerIndex]
return lessIndex + 1, largerIndex - 1
}

随机快排

只是比经典快排多了一行代码:index := rand.Intn(r-l+1) + l进行元素的随机选取

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
func QuickSort(nums []int) {
quickSort(nums, 0, len(nums)-1)
}

func quickSort(nums []int, l, r int) {
if l < r {
//如果这里加上一步:将随机选中的一个元素与最后一个元素交换就是我们的随机快排
index := rand.Intn(r-l+1) + l
nums[index], nums[r] = nums[r], nums[index]
l1, r1 := partition(nums, l, r)
quickSort(nums, l, l1-1)
quickSort(nums, r1+1, len(nums)-1)
}
}

//使用nums[R]作为划分
func partition(nums []int, L, R int) (int, int) {
//最开始没有小于等于范围没有数字,
lessIndex := L - 1
largerIndex := R
num := nums[R]
cur := L
for cur < largerIndex {
if nums[cur] < num {
nums[lessIndex+1], nums[cur] = nums[cur], nums[lessIndex+1]
lessIndex++
cur++
} else if nums[cur] > num {
nums[largerIndex-1], nums[cur] = nums[cur], nums[largerIndex-1]
largerIndex--
} else if nums[cur] == num {
cur++
}
}
//因为我们最后一个是没有排序的,所以大于的索引位置处与最后一个位置的元素交换即可
nums[largerIndex], nums[R] = nums[R], nums[largerIndex]
return lessIndex + 1, largerIndex - 1
}

评论