今天將單獨(dú)為大家介紹一下快速排序！

一、算法介紹

排序算法（Sorting algorithm）是計(jì)算機(jī)科學(xué)最古老、最基本的課題之一。要想成為合格的程序員，就必須理解和掌握各種排序算法。其中"快速排序"（Quicksort）使用得最廣泛，速度也較快。它是圖靈獎(jiǎng)得主C. A. R. Hoare(托尼·霍爾)于1960時(shí)提出來(lái)的。

二、算法原理

快排的實(shí)現(xiàn)方式多種多樣，豬哥給大家寫(xiě)一種容易理解的：分治+迭代，只需要三步：

在數(shù)列之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot），或者叫比較值。數(shù)列中所有元素都和這個(gè)基準(zhǔn)值進(jìn)行比較，如果比基準(zhǔn)值小就移到基準(zhǔn)值的左邊，如果比基準(zhǔn)值大就移到基準(zhǔn)值的右邊以基準(zhǔn)值左右兩邊的子列作為新數(shù)列，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。

舉個(gè)例子，假設(shè)我現(xiàn)在有一個(gè)數(shù)列需要使用快排來(lái)排序：{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}，我們來(lái)看看使用快排的詳細(xì)步驟：

選取中間的26作為基準(zhǔn)值（基準(zhǔn)值可以隨便選）數(shù)列從第一個(gè)元素3開(kāi)始和基準(zhǔn)值26進(jìn)行比較，小于基準(zhǔn)值，那么將它放入左邊的分區(qū)中，第二個(gè)元素44比基準(zhǔn)值26大，把它放入右邊的分區(qū)中，依次類(lèi)推就得到下圖中的第二列。然后依次對(duì)左右兩個(gè)分區(qū)進(jìn)行再分區(qū)，得到下圖中的第三列，依次往下，直到最后只有一個(gè)元素分解完成再一層一層返回，返回規(guī)則是：左邊分區(qū)+基準(zhǔn)值+右邊分區(qū)

三、代碼實(shí)現(xiàn)

是不是很簡(jiǎn)潔很秀，如果再有面試官讓你手寫(xiě)一個(gè)快排，你就把這行寫(xiě)上去吧，面試官見(jiàn)了都要喊你秀兒，哈哈。

在你感嘆python吊炸天的同時(shí)，你因該考慮到代碼的可讀性問(wèn)題，lambda函數(shù)設(shè)計(jì)是為了代碼的簡(jiǎn)潔性，但是濫用的話會(huì)導(dǎo)致可讀性變得極差，而且現(xiàn)在pep8代碼規(guī)范中也不建議使用lambda函數(shù)了，建議使用關(guān)鍵字def去定義一個(gè)函數(shù)，所以下面豬哥給大家寫(xiě)一段符合pythonic風(fēng)格的快排代碼

四、算法分析穩(wěn)定性：

快排是一種不穩(wěn)定排序，比如基準(zhǔn)值的前后都存在與基準(zhǔn)值相同的元素，那么相同值就會(huì)被放在一邊，這樣就打亂了之前的相對(duì)順序比較性：因?yàn)榕判驎r(shí)元素之間需要比較，所以是比較排序時(shí)間復(fù)雜度：快排的時(shí)間復(fù)雜度為O(nlogn)空間復(fù)雜度：排序時(shí)需要另外申請(qǐng)空間，并且隨著數(shù)列規(guī)模增大而增大，其復(fù)雜度為：O(nlogn)歸并排序與快排 ：歸并排序與快排兩種排序思想都是分而治之，但是它們分解和合并的策略不一樣：歸并是從中間直接將數(shù)列分成兩個(gè)，而快排是比較后將小的放左邊大的放右邊，所以在合并的時(shí)候歸并排序還是需要將兩個(gè)數(shù)列重新再次排序，而快排則是直接合并不再需要排序，所以快排比歸并排序更高效一些，可以從示意圖中比較二者之間的區(qū)別。

五、快排優(yōu)化

快速排序有一個(gè)缺點(diǎn)就是對(duì)于小規(guī)模的數(shù)據(jù)集性能不是很好?？赡苡腥苏J(rèn)為可以忽略這個(gè)缺點(diǎn)不計(jì)，因?yàn)榇蠖鄶?shù)排序都只要考慮大規(guī)模的適應(yīng)性就行了。但是快速排序算法使用了分治技術(shù)，最終來(lái)說(shuō)大的數(shù)據(jù)集都要分為小的數(shù)據(jù)集來(lái)進(jìn)行處理，所以快排分解到最后幾層性能不是很好，所以我們就可以使用揚(yáng)長(zhǎng)避短的策略去優(yōu)化快排：

先使用快排對(duì)數(shù)據(jù)集進(jìn)行排序，此時(shí)的數(shù)據(jù)集已經(jīng)達(dá)到了基本有序的狀態(tài)然后當(dāng)分區(qū)的規(guī)模達(dá)到一定小時(shí)，便停止快速排序算法，而是改用插入排序，因?yàn)槲覀冎爸v過(guò)插入排序在對(duì)基本有序的數(shù)據(jù)集排序有著接近線性的復(fù)雜度，性能比較好。

這一改進(jìn)被證明比持續(xù)使用快速排序算法要有效的多。

六、模擬面試面試官：

你了解快排嗎？你：略知一二面試官：那你講講快排的算法思想吧你：快排基本思想是：從數(shù)據(jù)集中選取一個(gè)基準(zhǔn)，然后讓數(shù)據(jù)集的每個(gè)元素和基準(zhǔn)值比較，小于基準(zhǔn)值的元素放入左邊分區(qū)大于基準(zhǔn)值的元素放入右邊分區(qū)，最后以左右兩邊分區(qū)為新的數(shù)據(jù)集進(jìn)行遞歸分區(qū)，直到只剩一個(gè)元素。面試官：快排有什么優(yōu)點(diǎn)，有什么缺點(diǎn)？你：分治思想的排序在處理大數(shù)據(jù)集量時(shí)效果比較好，小數(shù)據(jù)集性能差些。面試官：那該如何優(yōu)化？你：對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行快排，當(dāng)分區(qū)的規(guī)模達(dá)到一定小時(shí)改用插入排序，插入排序在小數(shù)據(jù)規(guī)模時(shí)排序性能較好。面試官：那你能手寫(xiě)一個(gè)快排嗎？你：

七、總結(jié)

以上所述是小編給大家介紹的Python一行代碼實(shí)現(xiàn)快速排序的方法,希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺(jué)得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

最新評(píng)論