圖解快速排序：Go 實現(xiàn)

1.什么是快速排序(Quick Sort)

快速排序是由東尼·霍爾所發(fā)展的一種排序算法.在平均狀況下,排序 n 個項目要 Ο(nlogn) 次比較.在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況并不常見. 事實上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因為它的內部循環(huán)(inner loop)可以在大部分的架構上很有效率地被實現(xiàn)出來.

快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists).

快速排序又是一種分而治之思想在排序算法上的典型應用.本質上來看,快速排序應該算是在冒泡排序基礎上的遞歸分治法

2.算法步驟

1. 從數(shù)列中挑出一個元素,稱為 “基準”(pivot)
2. 重新排序數(shù)列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數(shù)可以到任一邊).在這個分區(qū)退出之后,該基準就處于數(shù)列的中間位置.這個稱為分區(qū)(partition)操作；
3. 遞歸地(recursive)把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；

遞歸的最底部情形,是數(shù)列的大小是零或一,也就是永遠都已經(jīng)被排序好了. 雖然一直遞歸下去,但是這個算法總會退出,因為在每次的迭代(iteration)中,它至少會把一個元素擺到它最后的位置去.

3. Golang代碼實現(xiàn)

func?partition(list?[]int,?low,?high?int)?int?{
?pivot?:=?list[low]?//導致?low?位置值為空
?for?low???//high指針值?>=?pivot?high指針?移
??for?low????high--
??}
??//填補low位置空值
??//high指針值?
??//high?位置值空
??list[low]?=?list[high]
??//low指針值?<=?pivot?low指針?移
??for?low?=?list[low]?{
???low++
??}
??//填補high位置空值
??//low指針值?>?pivot?low值?移到high位置
??//low位置值空
??list[high]?=?list[low]
?}
?//pivot?填補?low位置的空值
?list[low]?=?pivot
?return?low
}

func?QuickSort(list?[]int,low,high?int)??{
?if?high?>?low{
??//位置劃分
??pivot?:=?partition(list,low,high)
??//左邊部分排序
??QuickSort(list,low,pivot-1)
??//右邊排序
??QuickSort(list,pivot+1,high)
?}
}

func?TestQuickSort(t?*testing.T)?{
?list?:=?[]int{2,44,4,8,33,1,22,-11,6,34,55,54,9}
?QuickSort(list,0,len(list)-1)
?t.Log(list)
}