建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
快速排序作為我們經(jīng)常在數(shù)據(jù)結(jié)構(gòu)面試中見(jiàn)到的算法，我們對(duì)它的理解和掌握是非常重要的，下面我用一段簡(jiǎn)單的步驟描述圖解以及代碼描述來(lái)帶大家快速的理解它。
10多年的永新網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷(xiāo)推廣的優(yōu)勢(shì)是能夠根據(jù)用戶(hù)設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整永新建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“永新網(wǎng)站設(shè)計(jì)”,“永新網(wǎng)站推廣”以來(lái)，每個(gè)客戶(hù)項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
快速排序（英語(yǔ)：Quicksort），又稱(chēng)劃分交換排序（partition-exchange sort）。
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
步驟為：
1，從數(shù)列中挑出一個(gè)元素，稱(chēng)為"基準(zhǔn)"（pivot），
2，重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作。
3，遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
import random def quick_sort(alist,start,end): if start>end: return # 如果前值大于后值則排序停止 此時(shí)low指針和high指針重合 low = start high = end middle = alist[start] # middle 是我們開(kāi)始時(shí)定的基準(zhǔn)的值而low和high表示指針的位置 while low < high: while low < high and alist[high] >= middle: high -= 1 alist[low] = alist[high] while low < high and alist[low] <= middle: low += 1 alist[high] = alist[low] # 當(dāng)退出循環(huán)的時(shí)候，證明low指針指向的數(shù)據(jù)有大于基準(zhǔn)middle的，所以講這個(gè)大于middle的數(shù)和high的位置進(jìn)行交換 alist[low] = middle # 推出循環(huán)之后，low和high的位置重合，此時(shí)這個(gè)重合的位置就是middle元素應(yīng)該在的位置，此時(shí)將middle放置此處，一次大循環(huán)結(jié)束 quick_sort(alist, start, low-1) quick_sort(alist, low+1,end) list1=[] # 用生成隨機(jī)數(shù)的方法去驗(yàn)證我們的排序算法 for i in range(30): list1.append(random.randint(1, 300)) quick_sort(list1, 0, len(list1)-1) print(list1)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定
從一開(kāi)始快速排序平均需要花費(fèi)O(n log n)時(shí)間的描述并不明顯。但是不難觀(guān)察到的是分區(qū)運(yùn)算，數(shù)組的元素都會(huì)在每次循環(huán)中走過(guò)一次，使用O(n)的時(shí)間。在使用結(jié)合的版本中，這項(xiàng)運(yùn)算也是O(n)。
在最好的情況，每次我們運(yùn)行一次分區(qū)，我們會(huì)把一個(gè)數(shù)列分為兩個(gè)幾近相等的片段。
這個(gè)意思就是每次遞歸調(diào)用處理一半大小的數(shù)列。
因此，在到達(dá)大小為一的數(shù)列前，我們只要作log n次嵌套的調(diào)用。
這個(gè)意思就是調(diào)用樹(shù)的深度是O(log n)。
但是在同一層次結(jié)構(gòu)的兩個(gè)程序調(diào)用中，不會(huì)處理到原來(lái)數(shù)列的相同部分；因此，程序調(diào)用的每一層次結(jié)構(gòu)總共全部?jī)H需要O(n)的時(shí)間（每個(gè)調(diào)用有某些共同的額外耗費(fèi)，但是因?yàn)樵诿恳粚哟谓Y(jié)構(gòu)僅僅只有O(n)個(gè)調(diào)用，這些被歸納在O(n)系數(shù)中）。
結(jié)果是這個(gè)算法僅需使用O(n log n)時(shí)間。
更多python知識(shí)，請(qǐng)關(guān)注Python視頻教程！！
名稱(chēng)欄目：創(chuàng)新互聯(lián)Python教程：Python帶你極速理解快速排序！
文章來(lái)源：http://www.dlmjj.cn/article/cddopoh.html
