用go语言实现一个快速排序算法
时间: 2024-05-16 10:19:54 浏览: 139
快速排序算法实现
以下是使用 Go 语言实现快速排序算法的示例代码:
```go
package main
import "fmt"
func quickSort(arr []int, left, right int) {
if left < right {
pivot := partition(arr, left, right)
quickSort(arr, left, pivot-1)
quickSort(arr, pivot+1, right)
}
}
func partition(arr []int, left, right int) int {
pivot := arr[right]
i := left - 1
for j := left; j < right; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[right] = arr[right], arr[i+1]
return i + 1
}
func main() {
arr := []int{8, 5, 1, 9, 7, 6, 3, 2, 4}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
```
该示例代码定义了两个函数 `quickSort` 和 `partition`。`quickSort` 函数是递归的实现快速排序的主要函数。在该函数中,首先调用 `partition` 函数将数组分为两个部分,然后再对左半部分和右半部分分别调用 `quickSort` 函数进行排序。
`partition` 函数是快速排序算法的核心。该函数通过一个基准值(pivot)将数组分为两个部分,使得左半部分的所有元素都小于基准值,右半部分的所有元素都大于等于基准值。在该函数中,首先取最右边的元素作为基准值,然后定义两个指针 `i` 和 `j`,分别指向左半部分的最后一个元素和右半部分的第一个元素。接着从左向右遍历数组,如果当前元素小于基准值,则将该元素与 `i` 指针指向的元素交换,然后将 `i` 指针向右移动一位。最后,将基准值与 `i+1` 指针指向的元素交换,然后返回 `i+1`。
在主函数 `main` 中,定义了一个整数数组 `arr`,然后调用 `quickSort` 函数对该数组进行排序。最后输出排序后的数组。
阅读全文