快排和归并是使用比较广泛的两种排序算法，他们的性能都可以达到O(nlgn)，这也是基于排序的算法能达到的最佳的性能。
快速排序
快速排序的递归描述如下：
对序列L排序时
- 如果L为空，则排序结果为空
- 否则，在L中任选一个元素作为pivot，然后递归的将L中不大于pivot的元素排序，将结果置于pivot左侧，同时递归地将所有大于pivot的元素排序，将结果置于pivot的右侧。
递归的基本快速排序算法实现如下:
package main
import "fmt"
func quickSort(source []int, l, u int) {
if l < u {
m := partition(source, l, u)
quickSort(source, l, m-1)
quickSort(source, m, u)
}
}
func partition(source []int, l, u int) int { //划分
var (
pivot = source[l]
left = l
right = l+1
)
for ;right<u; right++ {
if source[right] <= pivot {
left++
source[left], source[right] = source[right], source[left]
}
}
source[l], source[left] = source[left], source[l]
return left+1
}
func main() {
s := []int{10, 6, 7, 4, 2, 5}
quickSort(s, 0, len(s))
fmt.Println(s)
}
快速排序性能分析
最好情况
总共分为lgn层递归。 第一层划分，处理n个元素, 花费的时间复杂度为O(n)；第二层进行了2次划分，处理了n/2个元素，总体执行时间为2O(n/2)=O(n); 第三层进行了4次划分，处理了n/4个元素， 总体的执行时间为4O(n/4)=O(n);...。将上述时间想加，可以得到快速排序最快的时间复杂度是O(nlgn)。
最差情况
在最坏的情况下， 划分过程大部分时间把序列划分成了两个不平衡的部分。其中一部分的长度为O(1)，另一部分的长度为O(n)。 如果我们用图来表示， 最好的情况下，快速排序的过程形成了一颗平衡二叉树， 最坏的情况下， 快速排序的过程退化成了链表。
最坏情况下的时间复杂度也就是O(n^2)。
最坏情况下何时发生？
1、 序列中元素都相同或者大部分相同
2、 需要排序的序列处于相反的序列
3、其他一些情况也可能导致性能很差
平均情况
快速排序在平均情况下性能良好，甚至每次划分时总体得到1：9的两部分，总体性能仍然为O(nlgn)。
双向划分
在所有元素都相等的极端情况下， 双向划分可以将数组划分为两段长度相等的子数组， 虽然发生了n/2次不必要的交换，但因为总体划分是平衡的， 所以总体的时间复杂度还为: O(nlgn)
双向划分的代码如下：
package main
import "fmt"
func quickSort(source []int, l, u int) {
if l < u-1 {
m := partition(source, l, u)
quickSort(source, l, m-1)
quickSort(source, m, u)
}
}
func partition(source []int, l, u int) int { //双向划分
var (
pivot = source[l]
left = l
right = u
)
for {
left++
for left<u && source[left]<pivot {
left++
}
right--
for right>=l && source[right]>pivot {
right--
}
if left>=right {
break
}
source[left], source[right] = source[right], source[left]
}
source[l], source[right] = source[right], source[l]
return right+1
}
func main() {
s := []int{10, 6, 7, 4, 2, 5, 10}
quickSort(s, 0, len(s))
fmt.Println(s)
}
三路划分
显然， 我们应该避免对重复元素进行不必要的交换。 我们可以利用“三路划分”思路来改进算法，所有严格小于pivot的元素放在左侧子序列片段， 严格大于pivot的元素放入右侧， 而中间部分包含等于pivot的元素。
具体算法实现如下：
func quickSort2(source []int, l, u int) {
var (
i, j, p, q, pivot int
)
if l < u-1 {
i, p = l, l
j, q = u, u
pivot = source[l]
for {
i++
for i<u && source[i]<pivot {
i++
}
j--
for j>=l && source[j]>pivot {
j--
}
if i>=j {
break
}
source[i], source[j] = source[j], source[i]
if source[i] == pivot {
p++
source[p], source[i] = source[i], source[p]
}
if source[j] == pivot {
q--
source[q], source[j] = source[j], source[q]
}
}
if i==j && source[i] == pivot { //特殊情况
j--
i++
}
for k:=l; k<=p; k++ {
source[k], source[j] = source[j], source[k]
j--
}
for k:=u-1; k>=q; k-- {
source[k], source[i] = source[i], source[k]
i++
}
quickSort2(source, l, j+1)
quickSort2(source, i, u)
}
}
上面的代码在处理的时候要考虑很多边界条件， 下面是精简版本的代码，但交换操作增加了:
func quickSort3(source []int, l, u int) {
var (
i, j, k, pivot int
)
if l < u-1 {
i = l
j = u
pivot = source[l]
for k=l+1; k<j; k++ {
for pivot<source[k] {
j--
source[j], source[k] = source[k], source[j]
}
if source[k] < pivot {
source[k], source[i] = source[i], source[k]
i++
}
}
quickSort3(source, l, i)
quickSort3(source, k, u)
}
}
