演算法 in Golang：Quicksort（快速排序）
Quicksort（快速排序）
- 快速排序 O(nlog2^n)，比選擇排序要快 O(n2)
- 在日常生活中經常使用
- 使用了 D & C 策略（分而治之）
使用 Quicksort 排序陣列
- 不需要排序的陣列（也就是 Base Case 基線條件）：
- []，空陣列
- [s]，單元素陣列
- 很容易排序的陣列：
- [a, b]，兩個元素的陣列，只需檢查它們之間的大小即可，調換位置
- 3 個元素的陣列（例如 [23, 19, 35]）：
- 使用 D & C 策略，簡化至基線條件（Base case）
-
從陣列中隨便選一個元素，例如 35，這個元素叫做 pivot（基準元素）
-
找到比 pivot 小的元素，找到比 pivot 大的元素，這叫做磁區：[23, 19], (35), []
-
如果左右兩個子陣列已排好序（達到基線條件），結果：左邊 + [pivot] + 右邊
-
如果左右兩個子陣列沒排好序（沒達到基線條件），那么：
quicksort(左邊) + [pivot] + quicksort(右邊)
使用 Quicksort 排序陣列的步驟
- 選擇一個 pivot
- 將陣列分為兩個子陣列：
- 左側陣列的元素都比 pivot 小
- 右側陣列的元素都比 pivot 大
- 在兩個子陣列上遞回的呼叫 quicksort
創建專案
~/Code/go via ?? v1.20.3 via ?? base
? mcd quicksort
Code/go/quicksort via ?? v1.20.3 via ?? base
? go mod init quicksort
go: creating new go.mod: module quicksort
Code/go/quicksort via ?? v1.20.3 via ?? base
? c
Code/go/quicksort via ?? v1.20.3 via ?? base
?
main.go 代碼
package main
import "fmt"
func main() {
arr := []int{12, 87, 1, 66, 30, 126, 328, 12, 653, 67, 98, 3, 256, 5, 1, 1, 99, 109, 17, 70, 4}
result := quicksort(arr)
fmt.Println("result: ", result)
}
func quicksort(arr []int) []int {
if len(arr) < 2 {
return arr
}
pivot := arr[0]
var left, right []int
for _, ele := range arr[1:] {
if ele <= pivot {
left = append(left, ele)
} else {
right = append(right, ele)
}
}
return append(quicksort(left), append([]int{pivot}, quicksort(right)...)...)
}
運行
Code/go/quicksort via ?? v1.20.3 via ?? base
? go run main.go
result: [1 1 1 3 4 5 12 12 17 30 66 67 70 87 98 99 109 126 256 328 653]
Code/go/quicksort via ?? v1.20.3 via ?? base took 3.2s
?
本文來自博客園，作者：尋月隱君，轉載請注明原文鏈接：https://www.cnblogs.com/QiaoPengjun/p/17461882.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554484.html
標籤：其他
上一篇：Java中的金錢陷阱
下一篇：返回列表