Go 語言實(shí)現(xiàn)快速排序算法
作者：yongxinz
快速排序使用分治思想，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
快速排序是由東尼·霍爾所發(fā)明的一種排序算法，時(shí)間復(fù)雜度是 O(nlogn)， 是不穩(wěn)定排序算法。
快速排序使用分治思想，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
算法演示
通過動(dòng)圖來演示一下這個(gè)算法的執(zhí)行過程：
- 從數(shù)列中挑出一個(gè)元素，作為基準(zhǔn)（pivot）。
- 重新排序數(shù)列，所有比基準(zhǔn)小的值放到基準(zhǔn)前面，所有比基準(zhǔn)大的值放到基準(zhǔn)后面。排序之后，基準(zhǔn)值便處于數(shù)列的中間位置，這個(gè)過程稱為分區(qū)。
- 再遞歸對(duì)兩個(gè)子序列分別進(jìn)行排序操作。
Go 語言實(shí)現(xiàn)
代碼如下：
package main
import "fmt"
func partition(list []int, low, high int) int {
// 選擇基準(zhǔn)值
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 {
// 分區(qū)
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)
}以上就是本文的全部內(nèi)容。
參考文章：
- https://mojotv.cn/algorithm/golang-quick-sort。
責(zé)任編輯：姜華
來源：
AlwaysBeta
