33 lines
832 B
Go
33 lines
832 B
Go
|
package main
|
||
|
|
|
||
|
|
import "fmt"
|
||
|
|
|
||
|
|
func main() {
|
||
|
|
arr := []int{2, 35, 5, 33, 7, 8, 9, -2}
|
||
|
|
fmt.Println(partition(arr, 0, len(arr)-1))
|
||
|
|
fmt.Println("排序结果:", arr) // 输出: [-2 2 5 7 8 9 33 35]
|
||
|
|
}
|
||
|
|
|
||
|
|
func quickSort(arr []int, low, high int) {
|
||
|
|
if low >= high {
|
||
|
|
return
|
||
|
|
}
|
||
|
|
pivotIndex := partition(arr, low, high)
|
||
|
|
quickSort(arr, low, pivotIndex-1) // 递归左子数组
|
||
|
|
quickSort(arr, pivotIndex+1, high) // 递归右子数组
|
||
|
|
}
|
||
|
|
|
||
|
|
func partition(arr []int, low, high int) int {
|
||
|
|
pivot := arr[high] // 选择最后一个元素为基准值
|
||
|
|
i := low - 1 // i标记小于基准值的边界
|
||
|
|
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
|
||
|
|
}
|