快速排序是一种常用的内部排序算法，平均时间复杂度为 O(nlogn)。
算法思路
快速排序使用分治法来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。步骤如下：
- 挑选基准值: 从序列中选择任意一个元素作为基准，通常选择序列的第一个元素。
- 分割序列: 将序列中比基准元素小的元素放到基准前面，大的放在基准后面。
- 递归排序: 对较小的和较大的子序列分别进行上述操作。
举例说明
例如对序列 [ 3, 5, 4, 1, 2, 6 ] 进行快速排序
-
选取元素 3 作为基准元素。
-
将比 3 小的元素放在 3 前面，大的放在 3 后面，将其分割成两个子序列。
-
重复上述两个步骤，直到子序列划分完毕。
划分序列
序列划分有两种常用的方式。
方法一
从左到右遍历并调整交换位置，用 offset 记录偏移的量，用于填充基准元素。
-
初始化 offset 基准元素后的第一个位置 ( 即 offset = low + 1 )，从 offset 位置开始往后扫描，找到比 3 小的元素 1，交换 1 和基准外第一个位置的元素 5，交换后 offset 自增。
-
找到比 3 小的元素 2，交换 2 和基准外第二个位置的元素 4，交换后 offset 自增。
-
将基准元素与 offset - 1 位置处元素交换位置，既可将序列划分成两部分。
方法二
从两端向中间遍历，用变量缓存基准元素。
-
将序列第一个元素 2 当做基准元素，定义 pivot 变量缓存基准元素的值，并使 low 和 high 分别赋值为第一个元素和最后一个元素的索引。
-
从后往前找到第一个比基准元素小的元素 2，将其赋值给 s[low]。
-
从前往前后到第一个比基准元素大的元素 5，将其赋值给 s[high]。
-
从后往前找到第一个比基准元素小的元素 1，将其赋值给 s[low]。
-
从前往前后到第一个比基准元素大的元素 4，将其赋值给 s[high]。
-
到达终止条件，将 pivot 赋值给 s[low]，即可将序列划分成两部分。
具体实现
分割序列，递归划分子序列
func Sort(s []int, low, high int) {
if low < high {
// 分割序列，返回基准元素索引
pivot := partition(s, low, high)
// 递归分割左侧
Sort(s, low, pivot-1)
// 递归分割右侧
Sort(s, pivot+1, high)
}
}
方法一
第一种分割方式实现
func partition(s []int, low, high int) int {
pivot := low
offset := pivot + 1
// 从前往后寻找
for i := offset; i <= high; i++ {
if s[i] < s[pivot] {
s[i], s[offset] = s[offset], s[i]
offset++
}
}
s[pivot], s[offset-1] = s[offset-1], s[pivot]
return offset - 1
}
方法二
第二种分割方式实现
func partition(s []int, low, high int) int {
pivot := s[low]
for low < high {
// 从后往前找比基准元素小的元素的索引
for low < high && s[high] >= pivot {
high--
}
s[low] = s[high]
// 从前往后找比基准元素小的元素的索引
for low < high && s[low] <= pivot {
low ++
}
s[high] = s[low]
}
// 将基准元素插入两个子序列中间
s[low] = pivot
return low
}
单元测试
package quicksort
import "testing"
func TestSort(t *testing.T) {
testCase := []struct {
input []int
expected []int
}{
{[]int{3}, []int{3}},
{[]int{2, 1}, []int{1, 2}},
{[]int{1, 3, 1, 2}, []int{1, 1, 2, 3}},
{[]int{3, 1, 4, 2}, []int{1, 2, 3, 4}},
}
for _, c := range testCase {
res := Sort(c.input, 0, len(c.input)-1)
if !equal(res, c.expected) {
t.Fatalf("values = %v, expected %v", res, c.expected)
}
}
}
func equal(a, b []int) bool {
if len(a) != len(b) {
return false
}
for idx := 0; idx < len(a); idx++ {
if a[idx] != a[idx] {
return false
}
}
return true
}