快排和归并是使用比较广泛的两种排序算法，他们的性能都可以达到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)
    }
}