Golang（排序篇） —— 快速排序

Golang（排序篇） —— 快速排序

快速排序思想

1．先从数列中取出一个数作为基准数。（任意位置）

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

重复第二步，直到所有元素均排序完毕。

复杂度

时间复杂度： O(nlogn)

空间复杂度：

• 最坏情况 —— O(n)
• 最优情况 —— O(logn)。

不稳定

Golang代码

package main

import (
	"fmt"
)

func quickSort(nums []int, left, right int) {
	if left >= right{
		return
	}
	i, j := left, right
	// i从左边开始遍历，j从右边开始遍历。
	p := nums[i]
	// 设置基准数
	for i < j{
		for i < j && nums[i] < p{
		// 寻找一个比基准数大的数
			i++
		}
		for i < j && nums[j] > p{
		// 寻找一个比基准数小的数
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
		// 替换这两个数
	}
	nums[j] = p
	// 如果i和j相遇，就将基准数和j下标的值进行替换
	
	quickSort(nums, left, i-1)
	quickSort(nums, i+1, right)
}

func main() {
	a := []int{6, 5,3,1,8,7,2,4}
	quickSort(a, 0, len(a)-1)
	fmt.Println(a)
}

运行结果：

参考链接 关于作者

作者的联系方式：

你也可以通过 | | 关注我的动态