golang快速排序的方法是什么

avatar
作者
筋斗云
阅读量: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函数会根据基准值将数组分成两个部分。它使用两个指针ij,指向数组的首尾。遍历数组,如果当前元素小于基准值,就将它与i指针指向的元素交换,并将i指针向后移动。遍历结束后,将基准值与i+1指针指向的元素交换,将基准值放到正确的位置上,并返回基准值的索引。

运行以上代码,输出结果为:[1 3 5 6 7 9],表示数组已经按照升序排列好了。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!