快速排序原理

快速排序使用分治法（Divide and conquer）策略，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终整个数据变成有序序列。

效率

平均时间复杂度 O(nlogn)
最坏O(n^2)当划分不均匀时候 逆序and排好序都是最坏情况
最好O(n) 当划分均匀
空间复杂度O(logn)

稳定性

快速排序是不稳定排序

快速排序的Go语言实现代码

package main

import "fmt"
import "time"
import "math/rand"

func quickSort(numArr []int,start int, end int){
    if start >= end {
        return
    }
    mid := numArr[start]
    left,right := start+1,end
    for left < right{
        for numArr[left] > mid && left < right{
            left++
        }
        for numArr[right] <= mid && left < right{
            right--
        }
        numArr[left],numArr[right] = numArr[right],numArr[left]
    }
    if numArr[left] < mid{
        left--
    }
    numArr[start],numArr[left] = numArr[left],numArr[start]
    quickSort(numArr,start,left-1)
    quickSort(numArr,left+1,end)
}

// 快速排序
func main(){
    numArr := make([]int,9)

    rand.Seed(time.Now().UnixNano())
    for i := range numArr{
        numArr[i] = rand.Intn(100)
    }
    fmt.Println("排序前数组：",numArr)
    quickSort(numArr,0,8)
    fmt.Println("排序后数组：",numArr)
}