快速排序（高效排序算法） —— 不穩(wěn)點?。?！

動態(tài)圖：

快速排序.gif

快速排序1.gif

一、概念：

原理：
??快速排序使用分治法（Divide and conquer）策略來把一個序列分為較小和較大的2個子序列，然后遞歸地排序兩個子序列。
步驟：
??1.挑選基準(zhǔn)值：從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”（pivot），
??2.分割：重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（與基準(zhǔn)值相等的數(shù)可以到任何一邊）。在這個分割結(jié)束之后，對基準(zhǔn)值的排序就已經(jīng)完成，
??3..遞歸排序子序列：遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序。
（如果基準(zhǔn)數(shù)是第一個，那就先從右邊開始比對，如果基準(zhǔn)數(shù)是最后一個，那就先從第一個比對）

二、基本操作（步驟）：

// 快速排序
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] //選擇第一個數(shù)（是l而不是1）為key
    for i < j {
        for i < j && a[j] > key { //從右向左找第一個小于key的值
            j--
        }
        if i < j {
            a[i] = a[j]   //a[i] 已經(jīng)復(fù)制給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)
}

三、時間復(fù)雜度與排序穩(wěn)定性

時間復(fù)雜度： O(nlog(n))

空間復(fù)雜度：O(log(n))

穩(wěn)定性：不穩(wěn)定

特點：
??快速排序在最壞的情況下時間復(fù)雜度是O(n**2),平均時間復(fù)雜度是O(nlogn)?？焖倥判蚧旧媳徽J(rèn)為是相同數(shù)量級的所有排序算法中，平均性能最好的。