Go 語言實現快速排序算法
快速排序是由東尼 · 霍爾所發明的一種排序算法，時間複雜度是 O(nlogn)， 是不穩定排序算法。
快速排序使用分治思想，通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
算法演示
通過動圖來演示一下這個算法的執行過程：
-
從數列中挑出一個元素，作爲基準（
pivot）； -
重新排序數列，所有比基準小的值放到基準前面，所有比基準大的值放到基準後面。排序之後，基準值便處於數列的中間位置，這個過程稱爲分區；
-
再遞歸對兩個子序列分別進行排序操作。
Go 語言實現
代碼如下：
package main
import "fmt"
func partition(list []int, low, high int) int {
// 選擇基準值
pivot := list[high]
for low < high {
// low 指針值 <= pivot low 指針右移
for low < high && pivot >= list[low] {
low++
}
// low 指針值 > pivot low 值移到 high 位置
list[high] = list[low]
// high 指針值 >= pivot high 指針左移
for low < high && pivot <= list[high] {
high--
}
// high 指針值 < pivot high 值移到 low 位置
list[low] = list[high]
}
// pivot 替換 high 值
list[high] = pivot
return high
}
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 main() {
list := []int{2, 44, 4, 8, 33, 1, 22, -11, 6, 34, 55, 54, 9}
QuickSort(list, 0, len(list)-1)
fmt.Println(list)
}以上就是本文的全部內容，如果覺得還不錯的話歡迎點贊，轉發和關注，感謝支持。
參考文章：
- https://mojotv.cn/algorithm/golang-quick-sort
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OaHrvRGyVEWEC4gyONan1Q