Golang中實現快速排序的方法如下:
package main
import "fmt"
func main() {
arr := []int{5, 9, 3, 1, 7, 6}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
func quickSort(arr []int, low, high int) {
if low < high {
pivot := partition(arr, low, high)
quickSort(arr, low, pivot-1)
quickSort(arr, pivot+1, high)
}
}
func partition(arr []int, low, high int) int {
pivot := arr[high]
i := low - 1
for j := low; j < high; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
}
以上是一個簡單的快速排序的實現。首先,定義了一個quickSort
函數,它使用遞歸的方式對數組進行排序。在quickSort
函數中,首先通過partition
函數找到一個基準值(這里選擇數組最后一個元素),然后將小于基準值的元素放到基準值的左邊,大于基準值的元素放到基準值的右邊。然后,遞歸調用quickSort
函數對左右兩個子數組進行排序。最終,數組會被排序成升序。
partition
函數會根據基準值將數組分成兩個部分。它使用兩個指針i
和j
,指向數組的首尾。遍歷數組,如果當前元素小于基準值,就將它與i
指針指向的元素交換,并將i
指針向后移動。遍歷結束后,將基準值與i+1
指針指向的元素交換,將基準值放到正確的位置上,并返回基準值的索引。
運行以上代碼,輸出結果為:[1 3 5 6 7 9]
,表示數組已經按照升序排列好了。