快速排序算法，又稱分治法；

1 對一組找個基準數；

2 將該組數分為小于、大于基準數置于左右兩側；

3 再對左右兩側做重復2的操作

平均時間復雜度是O(nlogn)

以下是Go的實現方式

package mainimport ("fmt")//時間復雜度：最壞的情況O(n*n)//            最好的情況O(nlogn)// 			  平均O(nlogn)//有臨時變量的情況func qsort(arr []int, lf, rg int){	i := lf	j := rg	tmp := arr[lf]	p := lf	for i < j {		for j > p && arr[j] >= tmp {			j--		}		if j > p {			arr[p] = arr[j]			p = j		}		for i < p && arr[i] < tmp {			i++		}		if i < p {			arr[p] = arr[i]			p = i		}	}	arr[p] = tmp	fmt.PRintln(arr, tmp)	if p > lf {		qsort(arr, lf, p - 1)	}	if rg > p {		qsort(arr, p + 1, rg)	}}//無臨時變量func qsort2(arr []int, lf, rg int){	if lf >= rg { //這個效率高		return	}	i, j := lf, rg	x := arr[lf]	for i < j {		for i < j && arr[j] > x {			j--		}		if i < j {			arr[i] = arr[j]			i++		}		for i < j && arr[i] < x {			i++		}		if i < j {			arr[j] = arr[i]			j--		}	}	arr[i] = x	fmt.Println(arr, x)	if i > lf {		qsort2(arr, lf, i)	}	if i < rg {		qsort2(arr, i + 1, rg)	}}func main() {	fmt.Println("hello world")	arr := []int{5, 8, 9, 6, 3, 4, 7, 2}	//qsort(arr, 0, len(arr) - 1)	qsort2(arr, 0, len(arr) - 1)	fmt.Println(arr)}qsort 的排序過程輸出：
D:/work/go/src>sort.exe[2 4 3 5 6 9 7 8] 5[2 4 3 5 6 9 7 8] 2[2 3 4 5 6 9 7 8] 4[2 3 4 5 6 9 7 8] 3[2 3 4 5 6 9 7 8] 6[2 3 4 5 6 8 7 9] 9[2 3 4 5 6 7 8 9] 8[2 3 4 5 6 7 8 9] 7[2 3 4 5 6 7 8 9]
qsort2的排序過程輸出：
#有 lf >= rg return 時D:/work/go/src>sort2.exe[2 4 3 5 6 9 7 8] 5[2 4 3 5 6 9 7 8] 2[2 3 4 5 6 9 7 8] 4[2 3 4 5 6 9 7 8] 3[2 3 4 5 6 9 7 8] 6[2 3 4 5 6 8 7 9] 9[2 3 4 5 6 7 8 9] 8[2 3 4 5 6 7 8 9] 7[2 3 4 5 6 7 8 9]#無lf >= rg return 時D:/work/go/src>go build -o sort2.exe sort.goD:/work/go/src>sort2.exe[2 4 3 5 6 9 7 8] 5[2 4 3 5 6 9 7 8] 2[2 3 4 5 6 9 7 8] 4[2 3 4 5 6 9 7 8] 3[2 3 4 5 6 9 7 8] 4[2 3 4 5 6 9 7 8] 5[2 3 4 5 6 9 7 8] 6[2 3 4 5 6 8 7 9] 9[2 3 4 5 6 7 8 9] 8[2 3 4 5 6 7 8 9] 7[2 3 4 5 6 7 8 9] 8[2 3 4 5 6 7 8 9] 9[2 3 4 5 6 7 8 9]
參考：
http://baike.baidu.com/link?url=F1Oc-mApRFTe1vN50nFvjUjONeXHAL32GKV2MLvyv6q73Fb13B_QzQrQesLYtF_WeqGoyewE-ONjYFtZDoQnEF_ji3951uC3v0cL2vRa9vA4Gc_LdO701FJaOZK5ngS6QpJyxlr-HZI7uQ0o-_jV0_
http://blog.csdn.net/morewindows/article/details/6684558