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