我要评论golang双指针快速排序
快速排序算法思想:选中间位置作为基准，比它值小的移动到左边，比它大的值移动到右边。然后把基准值和末位元素交换(方便比较和移动)。定义两个指针left(起始位置0), right(起始位置len(arr) - 2), 循环和基准值比较，每次比较确定一个位置，移动指针，直到不满足left <= right.
注意：快速排序是一种原地排序，不依赖额外空间复杂度，但不是稳定的排序
时间复杂度：平均为o(nlogn), 最慢为o(n^2)。粗略计算时间复杂度主要分为2个部分，分区(o(n))和递归(o(logn)), 相乘为o(nlogn)。
空间复杂度：o(1)
package main
import "fmt"
func quicksort(arr []int) {
if len(arr) <= 1 {
return
}
// 选中间位置作为基准，比它值小的移动到左边，比它大的值移动到右边
pivotindex := len(arr) / 2
pivot := arr[pivotindex]
arr[pivotindex], arr[len(arr)-1] = arr[len(arr)-1], arr[pivotindex]
left := 0
right := len(arr) - 2
for left <= right { // 每一轮移动一次指针
if arr[left] <= pivot {
left++
} else {
arr[left], arr[right] = arr[right], arr[left]
right--
}
}
pivotindex = left
arr[left], arr[len(arr)-1] = arr[len(arr)-1], arr[left]
quicksort(arr[:pivotindex])
quicksort(arr[pivotindex+1:])
}
func main() {
arr := []int{4, 1, 3, 5, 2}
quicksort(arr)
fmt.println(arr)
}扩展：
golang实现快速排序和归并排序以及堆排序算法全注释
douyin lsy_helloworld，已成功入职互联网大厂，请关注我，了解非科班的程序员的工作生活把
快速排序算法
快速排序算法步骤如下：
- 首先从一个数组里找一个基准
- 对数组进行遍历
- 把比基准小的放基准左边，把比基准大的放基准右边
- 以基准为分割点，分成两个数组重复1-4步骤
- 直到数组长度为1返回
func quicksort(data []int) {
//如果数组长度为1，返回
if len(data) <= 1 {
return
}
//设置基准为数组第一个元素
base := data[0]
//两个指针分别指向待交换首尾位置
l, r := 0, len(data)-1
//基准为第一个元素，比较的元素从第二个开始
for i := 1; i <= r; {
//如果比较元素大于基准元素，把该元素放到数组尾部，把尾部元素交换过来
//此时尾部的元素已经判断过比基准元素大，因此r--向前移动，
//而i所在的元素为新交换过来的还没有判断过大小，因此保持不动
if data[i] > base {
data[i], data[r] = data[r], data[i]
r--
} else {
//如果比较元素小于等于基准元素，则交换当前元素和基准元素的位置
//l指向的是基准元素，因此l++才能重新指向基准元素,i++判断下一个数
data[i], data[l] = data[l], data[i]
l++
i++
}
}
//此时l指向基准元素，l前面的元素都比l小，l后面的都比l大
//因此对l前面和后面的数组再次快排，直到子数组长度为1结束
quicksort(data[:l])
quicksort(data[l+1:])
}归并排序算法
步骤如下:
- 把数组二分为left和right
- 对left和right再次二分
- 直到数组长度为1返回
- 对于每两个子数组进行重排，按照大小添加
- 进行递归就行了
func mergesort(data []int) []int {
length := len(data)
//如果长度为1不可再分，就返回
if length <= 1 {
return data
}
//把数组一分为二
num := length / 2
//左边和右边的数组都要再分
left := mergesort(data[:num])
right := mergesort(data[num:])
//对于每对数组进行排序
return merge(left, right)
}
func merge(left, right []int) (result []int) {
//数组是从长度为1开始进行添加的，因此每个子数组都是有序的
l, r := 0, 0
//当两个数组都没有遍历完的时候，按照元素大小依次添加
for l < len(left) && r < len(right) {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
//一个数组遍历完比，把没有遍历完的数组直接添加进去
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}堆排序算法
func heapsort(array []int) {
m := len(array)
s := m / 2
for i := s; i > -1; i-- {
heap(array, i, m-1)
}
for i := m - 1; i > 0; i-- {
array[i], array[0] = array[0], array[i]
heap(array, 0, i-1)
}
}
func heap(array []int, i, end int) {
l := 2*i + 1
if l > end {
return
}
n := l
r := 2*i + 2
if r <= end && array[r] > array[l] {
n = r
}
if array[i] > array[n] {
return
}
array[n], array[i] = array[i], array[n]
heap(array, n, end)
}到此这篇关于golang双指针快速排序的文章就介绍到这了,更多相关golang双指针内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论