算法05:Golang快速排序Quick Sort
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.算法步驟
img
- 從數(shù)列中挑出一個(gè)元素,稱為 “基準(zhǔn)”(pivot)
- 重新排序數(shù)列,所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面,所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊).在這個(gè)分區(qū)退出之后,該基準(zhǔn)就處于數(shù)列的中間位置.這個(gè)稱為分區(qū)(partition)操作；
- 遞歸地(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)
img
func partition(list []int, low, high int) int {
pivot := list[low] //導(dǎo)致 low 位置值為空
for low < high {
//high指針值 >= pivot high指針移
for low < high && pivot <= list[high] {
high--
}
//填補(bǔ)low位置空值
//high指針值 < pivot high值 移到low位置
//high 位置值空
list[low] = list[high]
//low指針值 <= pivot low指針移
for low < high && pivot >= 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)
}
原文作者：Eric Zhou
原文鏈接：https://mojotv.cn/algorithm/golang-quick-sort
