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

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

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

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

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用.本質(zhì)上來(lái)看,快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法

2.算法步驟

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

遞歸的最底部情形,是數(shù)列的大小是零或一,也就是永遠(yuǎn)都已經(jīng)被排序好了. 雖然一直遞歸下去,但是這個(gè)算法總會(huì)退出,因?yàn)樵诿看蔚牡?iteration)中,它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去.

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

func?partition(list?[]int,?low,?high?int)?int?{
?pivot?:=?list[low]?//導(dǎo)致?low?位置值為空
?for?low???//high指針值?>=?pivot?high指針?移
??for?low????high--
??}
??//填補(bǔ)low位置空值
??//high指針值?
??//high?位置值空
??list[low]?=?list[high]
??//low指針值?<=?pivot?low指針?移
??for?low?=?list[low]?{
???low++
??}
??//填補(bǔ)high位置空值
??//low指針值?>?pivot?low值?移到high位置
??//low位置值空
??list[high]?=?list[low]
?}
?//pivot?填補(bǔ)?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)
}