快排算法是一種本地算法，（即不需要額外的內存空間，就地排序）
- 基本思想：
從這個數(shù)列里找一個數(shù)作為基準點（支點）跟其它的數(shù)進行對比，小于或等于這個支點數(shù)的都放到左邊，大的放到右邊。完成一次排序，然后依次遞歸，當起始下標和末尾下標相遇是，排序結束，即整列數(shù)已經(jīng)排列好了順序。 - 快排為什么快呢？
簡單的總結是：快排實現(xiàn)了最優(yōu)下界。比如著名的稱球問題12個小球有一個是壞的（輕或重）， 現(xiàn)在呢有一架天平，問最少可用多少次就能確定哪個小球是壞的，并且指出它是輕了還是重了。答案是三次，稱三次就能得出結論。等概率最優(yōu)。時間復雜度為O(nlgn)（n乘以以10為底n的對數(shù)） - 快排為什么好像不那么快呢？
當輸入的數(shù)列是一個已經(jīng)排序好的數(shù)列時（順序或逆序），就慢了，因為它無法找到一個支點是兩邊等分的，無法做到等概率化，這是快排的最壞的情況，快排此時傻眼中。。。時間復雜度為O(n*n)但是沒關系，下面第二種實現(xiàn)隨機化快排算法可以彌補這個缺憾, 它不再關心你的輸入數(shù)列是什么。
（1）基本快排算法，本示例用輸入數(shù)列的第一個值作為排序支點。
package main
import (
"fmt"
"math/rand"
)
func main() {
// get the random numbers
origin := rand.Perm(10)
fmt.Println("origin:", origin)
quickSort(origin, 0, len(origin))
fmt.Println("quick sort:", origin)
}
func quickSort(list []int, start, end int) {
if end-start > 1 {
// get the pivot
mid := partition(list, start, end)
// left sort
quickSort(list, start, mid)
// right sort
quickSort(list, mid+1, end)
}
}
func partition(list []int, begin, end int) (i int) {
cValue := list[begin]
i = begin
for j := i + 1; j < end; j++ {
if list[j] < cValue {
i++ // 這里一定要先加1后在交換值，因為支點現(xiàn)在不必交換，現(xiàn)在i 和 j（小于支點和大于支點）正在劃分邊界
list[j], list[i] = list[i], list[j]
fmt.Println("list:", list)
}
}
/* 到此，i和j的邊界已經(jīng)劃分完成，把i對應的值和支點對應的值交換后，就符合了快分的要求：i左邊對應的值都小于等于且右邊的都大于支點對應的值
此時i的值就是新的支點, 對應的值就是新的主元
*/
list[i], list[begin] = list[begin], list[i]
return i
}
結果：
root@slave2:~# go run quickSort.go
origin: [9 4 2 6 8 0 3 1 7 5]
quick sort: [0 1 2 3 4 5 6 7 8 9]
（2）隨機快速排序算法
這個需要讓每次的主元（就是那個被比較值）隨機。實現(xiàn)如下：
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
//origin := rand.Perm(20) //偽隨機數(shù)
origin := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
fmt.Println("origin:", origin)
randomQuickSort(origin, 0, len(origin))
fmt.Println("quick sort:", origin)
}
func randomQuickSort(list []int, start, end int) {
if end-start > 1 {
// get the pivot
mid := randomPartition(list, start, end)
randomQuickSort(list, start, mid)
randomQuickSort(list, mid+1, end)
}
}
func randomPartition(list []int, begin, end int) int {
// 生成真隨機數(shù)
i := randInt(begin, end)
fmt.Println("random number:", i)
// 下面這行是核心部分，隨機選擇主元， 如果沒有此次交換，就是普通快排
list[i], list[begin] = list[begin], list[i]
return partition(list, begin, end)
}
func partition(list []int, begin, end int) (i int) {
cValue := list[begin]
i = begin
for j := i + 1; j < end; j++ {
if list[j] < cValue {
i++
list[j], list[i] = list[i], list[j]
}
}
list[i], list[begin] = list[begin], list[i]
return i
}
// 真隨機數(shù)
func randInt(min, max int) int {
rand.Seed(time.Now().UnixNano())
return min + rand.Intn(max-min)
}
為了顯示隨機快排對有序數(shù)列的處理要優(yōu)于普通快排，特意輸入了0-10的有序數(shù)列，測試結果如下：
普通快排：
root@slave2:~# go run quickSort.go
origin: [1 2 3 4 5 6 7 8 9]
random number: 6
random number: 8
random number: 2
random number: 7
random number: 5
random number: 7
random number: 6
random number: 7
quick sort: [1 2 3 4 5 6 7 8 9]
隨機快排：
root@slave2:~# go run randomQuickSort.go
origin: [1 2 3 4 5 6 7 8 9]
random number: 7
random number: 6
random number: 4
random number: 1
random number: 2
quick sort: [1 2 3 4 5 6 7 8 9]
