目錄

1.什么是快速排序

2.核心思想

3.代碼實(shí)現(xiàn)

4.性能分析

1.什么是快速排序

快速排序（簡(jiǎn)稱(chēng) 快排），計(jì)算機(jī)科學(xué)詞匯，使用領(lǐng)域 Pascal，C++ 等語(yǔ)言，是對(duì)基本排序算法的升級(jí)。快排發(fā)明之后，也變成了一種常用的數(shù)組排序方式，應(yīng)用于各類(lèi)高頻的算法題中，是我們必須掌握的一種排序算法。

2.核心思想

快排通過(guò)多次比較和交換來(lái)實(shí)現(xiàn)排序，下面我們來(lái)模擬一下這個(gè)過(guò)程。比如：要對(duì)數(shù)組 12,49,30,3,49,5,17,2,11,49,22,49 進(jìn)行排序

首先，用指針對(duì)數(shù)組的數(shù)和分界值進(jìn)行比較，然后：

當(dāng)一趟排序以后，我們發(fā)現(xiàn)：分界值 12 已經(jīng)處于數(shù)組的中間位置。而分界值左邊的數(shù)小于分界值，右邊的數(shù)大于等于分界值。

這樣，每次排序都固定好一個(gè)中間數(shù)，而接下來(lái)要做的，就是對(duì)中間數(shù)的左右區(qū)間再次進(jìn)行同樣的排序，最終讓整個(gè)數(shù)組都變成有序的。

下面，我們用視頻來(lái)模擬快排的全過(guò)程：

3. 代碼實(shí)現(xiàn)

快排算法的實(shí)現(xiàn)有很多種，在此，為了和視頻保持一致，我們給出了同一種算法；其余的可以下來(lái)再學(xué)習(xí)，一般情況下，熟悉這一種就能覆蓋大部分算法題了。

結(jié)合上述的排序流程和視頻，我們用 Go 語(yǔ)言實(shí)現(xiàn)快排算法：

func QUickSort(a []nums, left, right int) {
 ? ?// 特殊情況處理
 ? ?if left >= right {
 ? ? ? ?return
 ? ?}
 ? ?// 獲取分界值的下標(biāo)，此時(shí)左邊都小于該分界值，右邊都大于或等于該分界值
 ? ?key := partition(a, left, right)
 ? ?// 對(duì)左邊進(jìn)行排序
 ? ?QuickSort(a, left, key-1)
 ? ?// 對(duì)右邊進(jìn)行排序
 ? ?QUickSort(a, key+1, right)
}

// 一趟排序，獲取分界值的下標(biāo)
func partition(a []nums, left, right int) int {
 // 分界值為第一個(gè)元素,idx為第2個(gè)元素
 ? ?key, idx := nums[left], left+1
 ? ?for j:=left+1; j<=right; j++ {
 ? ? ? ?if nums[j] < key {
 ? ? ? ? ? ?// 交換，idx+1
 ? ? ? ? ? ?strs[idx], strs[j] = strs[j], strs[idx]
 ? ? ? ? ? ?idx++
 ? ? ? ?}
 ? ?}
 ? ?nums[idx-1], nums[left] = nums[left], nums[idx-1]
 ? ?return idx-1
}

4.性能分析

快速排序的一趟排序是從左到右遍歷整個(gè)數(shù)組，因此一趟排序的時(shí)間復(fù)雜度為 O(n)；所以，整個(gè)快排的時(shí)間復(fù)雜度取決于我們排序的趟數(shù)。

理想情況是，每次劃分的中間數(shù)正好將數(shù)組平分，即兩邊的元素幾乎一樣多。這種情況下，我們對(duì)其遞歸排序時(shí)，只需要

最壞的情況是，每次選的中間數(shù)都是當(dāng)前序列的最小或者最大元素，這使得遞歸次數(shù)和數(shù)組長(zhǎng)度一樣多。因此，最壞情況下的時(shí)間復(fù)雜度為

為了改善最壞情況下的時(shí)間性能，我們可以采用三者值取中：即從 nums[left], nums[right] 和 nums[(left+right)/2] 中選取中間值來(lái)作為一趟排序的分界值。

或者，選取一個(gè)隨機(jī)數(shù)作為分界值，以避免該序列取到的分界值是數(shù)組中最大或者最小的。

因此，快排的平均復(fù)雜度為 O(nlogn)，該算法被認(rèn)為是目前最好的一種內(nèi)部排序方法。