算法05:Golang快速排序Quick Sort
1.什么是快速排序(Quick Sort)
快速排序是由東尼·霍爾所發展的一種排序算法.在平均狀況下,排序 n 個項目要 Ο(nlogn) 次比較.在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況并不常見. 事實上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來.
快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists).
快速排序又是一種分而治之思想在排序算法上的典型應用.本質上來看,快速排序應該算是在冒泡排序基礎上的遞歸分治法
2.算法步驟
img
- 從數列中挑出一個元素,稱為 “基準”(pivot)
- 重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊).在這個分區退出之后,該基準就處于數列的中間位置.這個稱為分區(partition)操作；
- 遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序；
遞歸的最底部情形,是數列的大小是零或一,也就是永遠都已經被排序好了. 雖然一直遞歸下去,但是這個算法總會退出,因為在每次的迭代(iteration)中,它至少會把一個元素擺到它最后的位置去.
3. Golang代碼實現
img
func partition(list []int, low, high int) int {
pivot := list[low] //導致 low 位置值為空
for low < high {
//high指針值 >= pivot high指針移
for low < high && pivot <= list[high] {
high--
}
//填補low位置空值
//high指針值 < pivot high值 移到low位置
//high 位置值空
list[low] = list[high]
//low指針值 <= pivot low指針移
for low < high && pivot >= 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)
}
原文作者：Eric Zhou
原文鏈接：https://mojotv.cn/algorithm/golang-quick-sort
