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]
,表示数组已经按照升序排列好了。