GO实现 快速排序算法

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

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