快速排序以及优化

经典快速排序

思路:选取数组中的第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