快速排序采用分治的思想，选择一个数为基数（如第一个数），遍历数组将大于基数的元素放在基数右侧，将小于基数的元素放在基数左侧，再将基数两侧的子数组按同样方法处理，依样重复处理直到子数组不能再分，最后就能得到一个升序的数组。
快速排序，最佳时间复杂度为 \(O(nlogn)\)，最差时间复杂度为 \(O(n^2)\)。，平均时间复杂度为 \(O(nlogn)\)。
不难看出，基本思路是划分子数组+递归，示例代码如下：
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
// 快速升序排序
func quickSort(data *[]int, l, r int) {
if l >= r {
return
}
// 找到划分的基准数位置 i
i := partition(data, l, r)
// 对 i 前面的进行递归排序
quickSort(data, l, i-1)
// 对 i 后面的进行递归排序
quickSort(data, i+1, r)
}
func partition(data *[]int, l, r int) int {
i, j := l, r
for i < j {
// 将 data[l] 作为基准数
for i < j && (*data)[j] >= (*data)[l] {
j--
}
for i < j && (*data)[i] <= (*data)[l] {
i++
}
// 此时，data[i] > data[l] > data[j]，需要交换data[i]和data[j]，使 data[i] < data[l]< data[j]
(*data)[i], (*data)[j] = (*data)[j], (*data)[i]
}
// 将基准数放到分界位置 i
(*data)[l], (*data)[i] = (*data)[i], (*data)[l]
return i
}
func main() {
var l = []int{10, 15, 3, 6, 7, 12, 2}
fmt.Println("original:", l)
quickSort(&l, 0, len(l)-1)
fmt.Println("asc result:", l)
}
输出：
1
2
original: [10 15 3 6 7 12 2]
asc: [2 3 6 7 10 12 15]
如果要实现倒序排序，只需修改 partition 函数的 j--,i++ 条件即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func partition(data *[]int, l, r int) int {
i, j := l, r
for i < j {
// 将 data[l] 作为基准数
for i < j && (*data)[j] <= (*data)[l] {
j--
}
for i < j && (*data)[i] >= (*data)[l] {
i++
}
// 此时，data[i] < data[l]< data[j]，需要交换data[i]和data[j]，使 data[i] > data[l]> data[j]
(*data)[i], (*data)[j] = (*data)[j], (*data)[i]
}
(*data)[l], (*data)[i] = (*data)[i], (*data)[l]
return i
}