给我一个go的排序算法
时间: 2024-02-03 14:11:23 浏览: 24
下面是一个基于插入排序的 Go 语言实现:
```go
func insertionSort(arr []int) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j = j - 1
}
arr[j+1] = key
}
}
```
该算法的时间复杂度为 O(n^2),其中 n 是数组的长度。它的原理是,将数组分为已排序区间和未排序区间,每次从未排序区间取出一个元素,插入到已排序区间的适当位置,直到未排序区间为空。
相关问题
我想要一个go语言的排序算法
以下是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{5, 4, 3, 2, 1}
fmt.Println(arr)
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
```
此代码实现了快速排序算法。在 `quickSort` 函数中,我们首先选择一个主元素(pivot),然后将数组分成两部分,左边的元素小于或等于主元素,右边的元素大于主元素。然后递归地对左右两部分进行快速排序。在 `partition` 函数中,我们使用 `i` 指针来记录小于等于主元素的位置,然后遍历数组,将小于等于主元素的元素移到 `i` 指针的左边。最后将主元素移到 `i+1` 位置,返回 `i+1` 作为新的主元素位置。
go语言写一个快速排序算法
以下是使用Go语言实现的快速排序算法:
```
package main
import "fmt"
// 快速排序函数
func quickSort(nums []int, left int, right int) {
if left >= right {
return
}
pivot := nums[left] // 选择左侧第一个元素作为基准值
i, j := left, right
for i < j {
// 从右往左找到第一个小于基准值的元素
for i < j && nums[j] >= pivot {
j--
}
nums[i] = nums[j] // 将该元素放到左侧
// 从左往右找到第一个大于基准值的元素
for i < j && nums[i] <= pivot {
i++
}
nums[j] = nums[i] // 将该元素放到右侧
}
nums[i] = pivot // 将基准值放到排序后的位置
quickSort(nums, left, i-1) // 对左侧进行递归排序
quickSort(nums, i+1, right) // 对右侧进行递归排序
}
func main() {
nums := []int{5, 3, 7, 2, 8, 4, 1, 9, 6}
quickSort(nums, 0, len(nums)-1)
fmt.Println(nums) // 输出排序后的数组
}
```
在上述代码中,我们定义了一个`quickSort()`函数来实现快速排序算法。该函数的参数包括待排序的数组`nums`、待排序区间的左右边界`left`和`right`。
我们首先选择左侧第一个元素作为基准值`pivot`,然后定义两个指针`i`和`j`分别指向待排序区间的左右边界。接着,我们从右往左找到第一个小于基准值的元素,将其放到待排序区间的左侧;然后从左往右找到第一个大于基准值的元素,将其放到待排序区间的右侧。重复执行上述过程,直到`i`和`j`相遇。
最后,我们将基准值`pivot`放到排序后的位置,即`nums[i]`的位置。接着,我们对左侧和右侧分别进行递归排序,直到待排序区间大小为1或0。
在`main()`函数中,我们定义一个待排序的数组`nums`,并对其进行快速排序。最后,我们输出排序后的数组。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)