介绍
快速排序是一种分治策略的排序算法，是由英国计算机科学家 Tony Hoare 发明的， 该算法被发布在 1961 年的 Communications of the ACM 国际计算机学会月刊。
注： ACM = Association for Computing Machinery，国际计算机学会，世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。
快速排序是对冒泡排序的一种改进，也属于交换类的排序算法。
实现步骤
快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤如下：
- 先从数列中取出一个数作为基准数。一般取第一个数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
时间复杂度
在最好情况下，每一轮都能平均切分，这样遍历元素只要 n/2 次就可以把数列分成两部分，每一轮的时间复杂度都是：O(n)
最差的情况下，每次都不能平均地切分，每次切分都因为基准数是最大的或者最小的，不能分成两个数列，这样时间复杂度变为了 T(n) = T(n-1) + O(n)，按照主定理计算可以知道时间复杂度为：O(n^2)。
在综合情况下，快速排序的平均时间复杂度为：O(nlogn)。
普通快速排序
// 普通快速排序
func SortQuick(array []int, begin, end int) {
if begin < end {
// 进行切分
loc := partition(array, begin, end)
// 对左部分进行快排
SortQuick(array, begin, loc-1)
// 对右部分进行快排
SortQuick(array, loc+1, end)
}
}
// 切分函数，并返回切分元素的下标
func partition(array []int, begin, end int) int {
i := begin + 1 // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
j := end // array[end]是数组的最后一位
// 没重合之前
for i < j {
if array[i] > array[begin] {
array[i], array[j] = array[j], array[i] // 交换
j--
} else {
i++
}
}
/* 跳出while循环后，i = j。
* 此时数组被分割成两个部分 --> array[begin+1] ~ array[i-1] < array[begin]
* --> array[i+1] ~ array[end] > array[begin]
* 这个时候将数组array分成两个部分，再将array[i]与array[begin]进行比较，决定array[i]的位置。
* 最后将array[i]与array[begin]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！
*/
if array[i] >= array[begin] { // 这里必须要取等“>=”，否则数组元素由相同的值组成时，会出现错误！
i--
}
array[begin], array[i] = array[i], array[begin]
return i
}
测试普通快速排序
func TestSortQuick(t *testing.T) {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 11, 22, 33}
SortQuick(list, 0, len(list)-1)
fmt.Println(list)
}
测试结果
=== RUN TestSortQuick
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortQuick (0.00s)
PASS
算法改进方案1
// 直接插入排序在小规模数组下效率极好，我们只需将 end-begin <= 4 的递归部分换成直接插入排序，这部分表示小数组排序。
func SortQuick1(array []int, begin, end int) {
if begin < end {
// 当数组小于 4 时使用直接插入排序
if end-begin <= 4 {
SortInsert(array[begin : end+1])
return
}
// 进行切分
loc := partition(array, begin, end)
// 对左部分进行快排
SortQuick1(array, begin, loc-1)
// 对右部分进行快排
SortQuick1(array, loc+1, end)
}
}
测试
func TestSortQuick1(t *testing.T) {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick1(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick1(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 11, 22, 33}
SortQuick1(list, 0, len(list)-1)
fmt.Println(list)
}
测试结果
=== RUN TestSortQuick1
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortQuick1 (0.00s)
PASS
改进方案2
// 三切分的快速排序
func SortQuick2(array []int, begin, end int) {
if begin < end {
// 三向切分函数，返回左边和右边下标
lt, gt := partition3(array, begin, end)
// 从lt到gt的部分是三切分的中间数列
// 左边三向快排
SortQuick2(array, begin, lt-1)
// 右边三向快排
SortQuick2(array, gt+1, end)
}
}
// 切分函数，并返回切分元素的下标
func partition3(array []int, begin, end int) (int, int) {
lt := begin // 左下标从第一位开始
gt := end // 右下标是数组的最后一位
i := begin + 1 // 中间下标，从第二位开始
v := array[begin] // 基准数
// 以中间坐标为准
for i <= gt {
if array[i] > v { // 大于基准数，那么交换，右指针左移
array[i], array[gt] = array[gt], array[i]
gt--
} else if array[i] < v { // 小于基准数，那么交换，左指针右移
array[i], array[lt] = array[lt], array[i]
lt++
i++
} else {
i++
}
}
return lt, gt
}
测试
func TestSortQuick2(t *testing.T) {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick2(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick2(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 11, 22, 33}
SortQuick2(list, 0, len(list)-1)
fmt.Println(list)
}
测试结果
=== RUN TestSortQuick2
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortQuick2 (0.00s)
PASS
改进方案3
// 伪尾递归快速排序
func SortQuick3(array []int, begin, end int) {
for begin < end {
// 进行切分
loc := partition(array, begin, end)
// 那边元素少先排哪边
if loc-begin < end-loc {
// 先排左边
SortQuick3(array, begin, loc-1)
begin = loc + 1
} else {
// 先排右边
SortQuick3(array, loc+1, end)
end = loc - 1
}
}
}
测试
func TestSortQuick3(t *testing.T) {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick3(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick3(list, 0, len(list)-1)
fmt.Println(list)
list = []int{-1, 11, 22, 33}
SortQuick3(list, 0, len(list)-1)
fmt.Println(list)
}
测试结果
=== RUN TestSortQuick3
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortQuick3 (0.00s)
PASS
改进方案4
// 非递归快速排序
func SortQuick4(array []int) {
// 人工栈
helpStack := new(LinkStack)
// 第一次初始化栈，推入下标0，len(array)-1，表示第一次对全数组范围切分
helpStack.Push(len(array) - 1)
helpStack.Push(0)
// 栈非空证明存在未排序的部分
for !helpStack.IsEmpty() {
// 出栈，对begin-end范围进行切分排序
begin := helpStack.Pop().(int) // 范围区间左边
end := helpStack.Pop().(int) // 范围
// 进行切分
loc := partition(array, begin, end)
// 右边范围入栈
if loc+1 < end {
helpStack.Push(end)
helpStack.Push(loc + 1)
}
// 左边返回入栈
if begin < loc-1 {
helpStack.Push(loc - 1)
helpStack.Push(begin)
}
}
}
测试
func TestSortQuick4(t *testing.T) {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick4(list)
fmt.Println(list)
list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuick4(list)
fmt.Println(list)
list = []int{-1, 11, 22, 33}
SortQuick4(list)
fmt.Println(list)
}
测试结果
=== RUN TestSortQuick4
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortQuick4 (0.00s)
PASS
改进方案5
// 非递归快速排序优化
func SortQuickGood(array []int) {
// 人工栈
helpStack := new(LinkStack)
// 第一次初始化栈，推入下标0，len(array)-1，表示第一次对全数组范围切分
helpStack.Push(len(array) - 1)
helpStack.Push(0)
// 栈非空证明存在未排序的部分
for !helpStack.IsEmpty() {
// 出栈，对begin-end范围进行切分排序
begin := helpStack.Pop().(int) // 范围区间左边
end := helpStack.Pop().(int) // 范围
// 进行切分
loc := partition(array, begin, end)
// 切分后右边范围大小
rSize := -1
// 切分后左边范围大小
lSize := -1
// 右边范围入栈
if loc+1 < end {
rSize = end - (loc + 1)
}
// 左边返回入栈
if begin < loc-1 {
lSize = loc - 1 - begin
}
// 两个范围，让范围小的先入栈，减少人工栈空间
if rSize != -1 && lSize != -1 {
if lSize > rSize {
helpStack.Push(end)
helpStack.Push(loc + 1)
helpStack.Push(loc - 1)
helpStack.Push(begin)
} else {
helpStack.Push(loc - 1)
helpStack.Push(begin)
helpStack.Push(end)
helpStack.Push(loc + 1)
}
} else {
if rSize != -1 {
helpStack.Push(end)
helpStack.Push(loc + 1)
}
if lSize != -1 {
helpStack.Push(loc - 1)
helpStack.Push(begin)
}
}
}
}
测试
func TestSortQuickGood(t *testing.T) {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuickGood(list)
fmt.Println(list)
list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SortQuickGood(list)
fmt.Println(list)
list = []int{-1, 11, 22, 33}
SortQuickGood(list)
fmt.Println(list)
}
测试结果
=== RUN TestSortQuickGood
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortQuickGood (0.00s)
PASS