快速排序代码

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
func QuickSort(array []int64)  {
// 数组长度小于1时直接返回
if len(array) <=1 {
return
}

// 定义最后一个值为轴
pivot := len(array)-1

// array[left]初始化为数组第一个值
left := 0

// array[right]初始化为轴的前一个值
right := pivot-1

// array[left]与array[pivot]进行对比,找到大于array[pivot]的值后记录left
// 之后开始array[right]与array[pivot]进行对比,找到小于等于array[pivot]的值与刚刚array[left]的值进行交换
// 直到array[left]与array[right]的值重合
for left < right {
for ; left < right && array[left] <= array[pivot]; left++ {}
for ; right > left && array[right] > array[pivot]; right-- {}
array[left], array[right] = array[right], array[left]
}

// 经过上一步的比对后,array[:left]的值全部都会小于等于array[pivot]
// 且array[left:pivot]的值都会大于array[pivot]
// 再经过下面这步操作后,array[:left+1]的值都会小于等于之前的array[pivot]
// 而array[left+1:]的值全都会大于之前的array[pivot]
if array[left] > array[pivot] {
array[pivot],array[left] = array[left], array[pivot]
}
QuickSort(array[:left+1])
QuickSort(array[left+1:])
}

快速排序算法平均时间复杂度O(nlog2n),最好时间复杂度为O(nlog2n),最差时间复杂度为O(n2)
空间复杂度O(log2n),稳定性为不稳定