快速排序——分治的表弟

配套視頻：快速排序——分治的表弟_嗶哩嗶哩_bilibili

主要思想：

? ? ? ? 快速排序是一種基于分治法的排序算法，它的思想就在于找一個(gè)“基準(zhǔn)”。 快速排序通過選擇一個(gè)基準(zhǔn)元素，然后將數(shù)組分為小于基準(zhǔn)元素和大于基準(zhǔn)元素的兩個(gè)子數(shù)組。接下來，對(duì)這兩個(gè)子數(shù)組再次進(jìn)行快速排序，一直這樣分下去，直到被排序的數(shù)組只剩兩個(gè)元素，結(jié)果就顯而易見了?？焖倥判虻暮诵脑谟谌绾芜x擇基準(zhǔn)元素以及如何將數(shù)組進(jìn)行劃分。一般來說，可以隨意選擇數(shù)組的元素作為基準(zhǔn)元素。然后，通過比較其他元素與基準(zhǔn)元素的大小，將它們劃分到相應(yīng)的子數(shù)組中。這個(gè)過程稱為劃分操作。

? ? ? ?兩個(gè)指針一起工作是將大問題一分為二的其中一個(gè)方法，在現(xiàn)實(shí)中，不一定要兩個(gè)指針，也可以用其他方法。在這個(gè)方法中，其中的兩個(gè)指針一個(gè)指向基準(zhǔn)，一個(gè)指向和基準(zhǔn)作比較的數(shù)，常用left（左）和right（右）來命名。

? ? ? ?由于快速排序是遞歸的，最壞情況發(fā)生在選擇的基準(zhǔn)元素總是最小或者最大的元素。為了避免最壞情況，可以采用隨機(jī)選擇基準(zhǔn)元素的方法，出現(xiàn)最壞元素的幾率也就減少了。

適用范圍：

? ? ? ?快速排序適用于需排序的場(chǎng)景，并且原數(shù)組能夠分解成若干個(gè)子數(shù)組，并且子數(shù)組可以用相同的方法繼續(xù)劃分下去，直到結(jié)果變得顯而易見為止。?

例題：

總結(jié)：

? ? ? ?總結(jié)一下，快速排序是基于分治法的排序算法，它通過選擇一個(gè)基準(zhǔn)元素并將數(shù)組劃分為兩個(gè)子數(shù)組來進(jìn)行排序?？焖倥判蚓哂泻芸斓乃俣?，并且是原地排序算法，不需要多余空間。然而，快速排序的最壞情況下將不再快速，很緩慢，所以需要注意避免最壞情況的發(fā)生。

? ? ? ?快速排序是一種高效的排序算法，通過選取基準(zhǔn)元素和劃分過程將序列不斷分割成更小的子序列，并對(duì)子序列進(jìn)行遞歸排序，最終完成整個(gè)序列的排序。在實(shí)際應(yīng)用中，快速排序被廣泛使用。他又稱“雙指針法”，使用了兩個(gè)指針，一個(gè)指向基準(zhǔn)，一個(gè)指向和基準(zhǔn)比對(duì)的數(shù)。

? ? ? 快速排序步驟大致分為“選取基準(zhǔn)元素”、“劃分”和“遞歸排序”三大步。

好啦，關(guān)于動(dòng)態(tài)規(guī)劃就說到這里。這里是康郭聊算法，拜拜！

#注：例題答案請(qǐng)查看視頻。