golang的快速排序怎么写
时间: 2023-02-20 15:19:17 浏览: 91
快速排序的原理是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
Go语言实现快速排序的代码如下:
func quickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := arr[0]
left := make([]int, 0)
right := make([]int, 0)
for i := 1; i < len(arr); i++ {
if arr[i] < mid {
left = append(left, arr[i])
} else {
right = append(right, arr[i])
}
}
left = quickSort(left)
right = quickSort(right)
left = append(left, mid)
left = append(left, right...)
return left
}
相关问题
golang快速排序
Go语言中实现快速排序的方法如下:
1. 首先,需要定义一个函数,该函数接受一个整型切片作为参数。
2. 然后,在函数内部定义两个指针,一个指向切片的第一个元素,另一个指向切片的最后一个元素。
3. 选取切片的第一个元素作为基准元素。
4. 使用两个指针遍历切片,如果左指针所指元素大于基准元素,而右指针所指元素小于基准元素,则交换它们。
5. 重复第4步,直到左指针和右指针相遇。
6. 交换基准元素和相遇点元素。
7. 对基准元素左边的切片和右边的切片重复以上步骤,直到切片中只有一个元素。
代码示例:
```
package main
import "fmt"
func quickSort(s []int, left, right int) {
if left < right {
pivot := partition(s, left, right)
quickSort(s, left, pivot-1)
quickSort(s, pivot+1, right)
}
}
func partition(s []int, left, right int) int {
pivot := s[right]
i := left - 1
for j := left; j < right; j++ {
if s[j] <= pivot {
i++
s[i], s[j] = s[j], s[i]
}
}
s[i+1], s[right] = s[right], s[i+1]
return i + 1
}
func main() {
s := []int{6, 2, 8, 1, 4, 9, 3, 7, 5}
quickSort(s, 0, len(s)-1)
fmt.Println(s)
}
```
用golang写快速排序
以下是用 Golang 实现的快速排序算法:
```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{9, 3, 2, 7, 6, 8, 1, 5, 4}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
```
在 `quickSort` 函数中,我们选择数组的最后一个元素作为枢轴(pivot),然后使用 `partition` 函数将数组分成两个部分。在 `partition` 函数中,我们从左到右遍历数组,如果发现当前元素小于枢轴,则将它与 `i` 指向的元素交换位置,并将 `i` 向右移动一位。最后,我们将枢轴与 `i+1` 指向的元素交换位置,并返回 `i+1`。
通过不断递归调用 `quickSort` 函数,我们可以不断地将数组分成更小的部分,最终实现排序。
阅读全文