快速排序被譽(yù)為20世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。聽名字就能了解，快速排序的特點(diǎn)，就是快

快速排序

快速排序采用了二分遞歸的思想，通過一趟排序?qū)⒄麄€(gè)數(shù)組劃分為兩個(gè)部分，低位部分的值全部小于高位部分的值，然后對低位和高位部分分別排序

快速排序算法的具體步驟如下：

1. 對數(shù)組 arr 進(jìn)行隨機(jī)洗牌

2. 劃分?jǐn)?shù)組，我們通過交換操作，找到合適的 j，保證

   • j 左邊的元素全部小于 arr[j]
   • j 右邊的元素全部大于 arr[j]

3. 對每一塊被劃分的切片進(jìn)行排序

qs1.png

我們可以通過雙指針在O(n)的時(shí)間復(fù)雜度內(nèi)獲取合適的 j

我們設(shè)立兩個(gè)指針 i 和 j，同時(shí)設(shè)置一個(gè)標(biāo)志值 arr[low]，一般來說，標(biāo)志值取數(shù)組第一個(gè)元素

• 當(dāng) arr[i] < arr[low]時(shí)，指針 i 從左至右一直掃描
• 當(dāng) arr[j] > arr[low]時(shí)，指針 j 從右至左一直掃描
• 交換 arr[i]和 a[j]的元素
• 當(dāng) i < j 時(shí)重復(fù)以上步驟

上述算法結(jié)束之后，j 所在的位置即為我們尋找的 j

golang代碼實(shí)現(xiàn)如下：

func partition(arr []int, low int, high int) int {
    i, j := low+1, high
    for true {
        for arr[i] < arr[low] {
            i++
            if i == high {
                break
            }
        }
        for arr[low] < arr[j] {
            j--
            if j == low {
                break
            }
        }
        if i >= j {
            break
        }
        exch(arr, i, j)
    }
    exch(arr, low, j)
    return j
}

對于整個(gè)快排算法，我們的 golang實(shí)現(xiàn)如下:

func quickSort(arr []int) []int {
    arr = shuffling(arr)
    sort(arr, 0, len(arr)-1)
    return arr
}

func sort(arr []int, low int, high int) {
    if high <= low {
        return
    }
    j := partition(arr, low, high)
    sort(arr, low, j-1)
    sort(arr, j+1, high)
}
func partition(arr []int, low int, high int) int {
    i, j := low+1, high
    for true {
        for arr[i] < arr[low] {
            i++
            if i == high {
                break
            }
        }
        for arr[low] < arr[j] {
            j--
            if j == low {
                break
            }
        }
        if i >= j {
            break
        }
        exch(arr, i, j)
    }
    exch(arr, low, j)
    return j
}
func exch(arr []int, a int, b int) {
    temp := arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

時(shí)間復(fù)雜度：

最好情況 O(nlogn)
最壞情況 O(n^2)

由于我們添加了洗牌方法（見基本排序?qū)崿F(xiàn)），所以整個(gè)數(shù)組趨向于無序，快速排序往往能取得比其他排序好的多的性能

參考文獻(xiàn)：
Dynamic Connectivity - 普林斯頓大學(xué) | Coursera