快速排序（高效排序算法） —— 不稳点！！！

动态图：

快速排序.gif

快速排序1.gif

一、概念：

原理：
  快速排序使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤：
  1.挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
  2.分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
  3..递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
（如果基准数是第一个，那就先从右边开始比对，如果基准数是最后一个，那就先从第一个比对）

二、基本操作（步骤）：

// 快速排序
package main

import (
    "fmt"
    "math/rand"
    "time"
)

//1.
const (
    num      = 100000
    rangeNum = 100000
)

func main() {
    // fmt.Println(time.Now().Unix() , time.Now().UnixNano())
    randSeed := rand.New(rand.NewSource(time.Now().Unix() + time.Now().UnixNano()))
    var buf []int
    for i := 0; i < num; i++ {
        buf = append(buf, randSeed.Intn(rangeNum))
    }
    t := time.Now()
    // 快速排序
    kuaisu(buf)
    fmt.Println(time.Since(t))  //求排序时间，与t := time.Now()配合
}
func kuaisu(buf []int) {
    kuai(buf, 0, len(buf)-1)
}

func kuai(a []int, l, r int) {
    if l >= r {
        return
    }
    i, j, key := l, r, a[l] //选择第一个数（是l而不是1）为key
    for i < j {
        for i < j && a[j] > key { //从右向左找第一个小于key的值
            j--
        }
        if i < j {
            a[i] = a[j]   //a[i] 已经复制给key，不会丢失
            i++
        }

        for i < j && a[i] < key { //从左向右找第一个大于key的值
            i++
        }
        if i < j {
            a[j] = a[i]
            j--
        }
    }
    //i == j
    a[i] = key
    kuai(a, l, i-1)
    kuai(a, i+1, r)
}

三、时间复杂度与排序稳定性

时间复杂度： O(nlog(n))

空间复杂度：O(log(n))

稳定性：不稳定

特点：
  快速排序在最坏的情况下时间复杂度是O(n**2),平均时间复杂度是O(nlogn)。快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。