go快速排序

时间复杂度:O(n²)

空间复杂度:O(Nlog2n)

不稳定,较复杂

过程:

1、设置一个基点,通常为最左边或最右边,下面设置为最左边,设置设置两个指针分别指向数组两端

2、先移动右边指针,如果小于基点的值,则停止移动,并且把值覆盖到最左边的指针的值

3、覆盖之后,把最左边的指针向右移动,如大于几点,则覆盖右边指针的值,直到 左右指针指向相同位置,则把几点赋值到指针所在位置

4、把当前指针所在位置当作中间点,然后拆分左右两段,分别重复(2\3)步骤即可(下面使用递归的方式进行重复处理)

/*** @author Yel* 快速排序* 时间复杂度:O(n²)* 空间复杂度:O(Nlog2n)* 不稳定,较复杂* 过程:* 1\设置一个基点,通常为最左边或最右边,下面设置为最左边,设置设置两个指针分别指向数组两端* 2\先移动右边指针,如果小于基点的值,则停止移动,并且把值覆盖到最左边的指针的值* 3\覆盖之后,把最左边的指针向右移动,如大于几点,则覆盖右边指针的值,直到 左右指针指向相同位置,则把几点赋值到指针所在位置* 4\把当前指针所在位置当作中间点,然后拆分左右两段,分别重复(2\3)步骤即可(下面使用递归的方式进行重复处理)*/
func Quicksort(arr []int, order string) {var length = len(arr)if length < 2 {return}var base = arr[0]                   // 使用左边第一个为基准var left, right int = 0, length - 1 // 设置左右指针for left != right {// 先把右指针向左移动,如果遇到小于基准的值,则覆盖左边位置for left < right {// 升序if order == "asc" {// 右边向左移动,遇到比基准小的,则覆盖左边位置if base > arr[right] {arr[left] = arr[right]break}} else {// 降序if base < arr[right] {arr[left] = arr[right]break}}right--}// fmt.Println(left, right)// 从左向右移动,找到比基准大的,覆盖右边位置for left < right {// 从左向右移动,找到比基准大的,覆盖右边位置// 升序if order == "asc" {if base < arr[left] {arr[right] = arr[left]break}} else {if base > arr[left] {arr[right] = arr[left]break}}left++}// fmt.Println(left, right)}// 指针左右相等,则把基准值放到指针位置arr[left] = base// 对数组左边进行快速排序Quicksort(arr[:left], order)// 对数组右边进行快速排序Quicksort(arr[left+1:], order)
}