1、常用排序算法
| 排序算法 | 平均時間 | 最差情形 | 穩(wěn)定度 | 備注 |
|---|---|---|---|---|
| 快速排序 | O(nlogn) | O(n^2) | 不穩(wěn)定 | n大時較好 |
| 冒泡排序 | O(n^2) | O(n^2) | 穩(wěn)定 | n小時較好 |
| 選擇排序 | O(n^2) | O(n^2) | 不穩(wěn)定 | n小時較好 |
| 插入排序 | O(n^2) | O(n^2) | 穩(wěn)定 | 大部分已排好序時較好 |
| 歸并排序 | O(nlogn) | O(nlogn) | 穩(wěn)定 | n大時較好 |
| 希爾排序 | O(nlogn) | O(n^s) 1<s<2 | 不穩(wěn)定 | s是所選分組 |
2济炎、快速排序法
基本思想：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分川抡，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序冻辩，整個排序過程可以遞歸進行猖腕，以此達到整個數(shù)據(jù)變成有序序列。注：快速排序不是一種穩(wěn)定的排序算法恨闪，也就是說倘感，多個相同的值的相對位置也許會在算法結(jié)束時產(chǎn)生變動。
-
一趟快速排序算法（首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)咙咽，然后將所有比它小的數(shù)都放到它前面老玛，所有比它大的數(shù)都放到它后面）步驟：
1）設(shè)置兩個變量i、j，排序開始的時候：i=0蜡豹，j=N-1（列表長度最后一個元素下標(biāo)）麸粮；
2）以第一個列表元素作為關(guān)鍵數(shù)據(jù)，賦值給key镜廉，即key=A[0]弄诲；
3）從j開始向前搜索，即由后開始向前搜索(j-=1)娇唯，找到第一個小于key的值A(chǔ)[j]齐遵，將A[j]和A[i]互換；
4）從i開始向后搜索塔插，即由前開始向后搜索(i+=1)梗摇，找到第一個大于key的A[i]，將A[i]和A[j]互換想许；
5）重復(fù)第3伶授、4步，直到i=j流纹； (3,4步中糜烹，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j捧颅、i的值柠新，使得j=j-1畅铭，i=i+1，直至找到為止。找到符合條件的值肩榕，進行交換的時候i绪氛， j位置不變懂傀。另外流强，i=j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結(jié)束）贮尖。
-
示例：
假設(shè)用戶輸入了如下數(shù)組：
下標(biāo) 0 1 2 3 4 5 數(shù)據(jù) 6 2 7 3 8 9 創(chuàng)建變量i=0（指向第一個數(shù)據(jù)）, j=5(指向最后一個數(shù)據(jù)), key=6(賦值為第一個數(shù)據(jù)的值)笛粘。
（1）要把所有比key小的數(shù)移動到key的左面，故先開始尋找比6小的數(shù)湿硝，從j開始薪前，從右往左找，不斷遞減變量j的值(j-=1)关斜，找到第一個下標(biāo)3的數(shù)據(jù)比6小示括，于是把數(shù)據(jù)3移到下標(biāo)0的位置(A[i]=A[j])，把下標(biāo)0的數(shù)據(jù)6移到下標(biāo)3痢畜，完成第一次比較：
下標(biāo) 0 1 2 3 4 5 數(shù)據(jù) 3 2 7 6 8 9 （2）i=0垛膝，j=3鳍侣，key=6，第二次比較（通俗來說：移動指針從j開始的吼拥，而因為第一個比較時倚聚，找到了值比key小，故該值由key的右邊移到了左邊凿可，稱做發(fā)生了“交叉變換”行為惑折，故移動指針變?yōu)閕了，要去找比key大的值了矿酵；說明：之后每發(fā)生一次所謂的“交叉變換”唬复，移動指針都要變化的），移動指針為i全肮，從前往后找，遞加變量i棘捣，發(fā)現(xiàn)下標(biāo)2的數(shù)據(jù)是第一個比key大的辜腺，于是用下標(biāo)2的數(shù)據(jù)7和j指向的下標(biāo)3的數(shù)據(jù)的6做交換，數(shù)據(jù)狀態(tài)變成下表：
下標(biāo) 0 1 2 3 4 5 數(shù)據(jù) 3 2 6 7 8 9 （3）i=2乍恐，j=3评疗，key=6，移動指針變?yōu)閖茵烈，故遞減變量j百匆，不斷重復(fù)進行上面的循環(huán)比較。
（4）直到i=j：都指向了下標(biāo)2呜投。于是加匈，第一遍比較結(jié)束。得到結(jié)果如下仑荐，凡是key(=6)左邊的數(shù)都比它小雕拼，凡是key右邊的數(shù)都比它大：
下標(biāo) 0 1 2 3 4 5 數(shù)據(jù) 3 2 6 7 8 9 如果i和j沒有碰頭的話，就遞加i找大的粘招，還沒有啥寇，就再遞減j找小的，如此反復(fù)洒扎，不斷循環(huán)辑甜。注意判斷和尋找是同時進行的。然后袍冷，對key兩邊的數(shù)據(jù)磷醋，再分組分別進行上述的過程，直到不能再分組為止难裆。
注意：第一遍快速排序不會直接得到最終結(jié)果子檀，只會把比key大和比key小的數(shù)分到key的兩邊镊掖。為了得到最后結(jié)果，需要再次對下標(biāo)2兩邊的數(shù)組分別執(zhí)行此步驟褂痰，然后再分解數(shù)組亩进，直到數(shù)組不能再分解為止（只有一個數(shù)據(jù)），才能得到正確結(jié)果缩歪。
-
Python代碼
def quickSort_main(data_list,i,j):#快速排序法主調(diào)用程序,調(diào)用開始時i=1,j=len(data_kist)-1 if i < j: split_point = quickSort_spec(data_list,i,j) quickSort_main(data_list,i,split_point) #遞歸 quickSort_main(data_list,split_point+1,j) def quickSort_spec(data_list,i,j):#快速排序具體過程 key = data_list[i] while i < j: while i < j and data_list[j]>=key: j-=1 data_list[i] = data_list[j]#不在循環(huán)里了归薛，即data_list[j]<key，要將j下標(biāo)對應(yīng)的值放到i位置 while i < j and data_list[i]<=key: i +=1 data_list[j] = data_list[i]#不在循環(huán)里了匪蝙，即data_list[i]>key主籍，要將i下標(biāo)對應(yīng)的值放到j(luò)位置 data_list[i] = key #此時i=j，即找到了key要放的位置 return i #返回key所在下標(biāo)位置 >>>data_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>>quickSort_main(data_list,0,len(data_list)-1) >>>print(data_list) [17, 20, 26, 31, 44, 54, 55, 77, 93]
3逛球、冒泡排序法
-
基本思想
每個回合都從第一個元素開始和它后面的元素比較千元，如果比它后面的元素更大的話就交換，一直重復(fù)颤绕，直到這個元素到達了所進行排序元素的最后位置幸海。繼續(xù)重復(fù)操作，每次遍歷都會將剩下的元素中最大的那個放到了序列的“最后”(除去了前面已經(jīng)排好的那些元素)奥务，即排序一次后大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（冒泡命名的來源）物独。算法時間復(fù)雜度為O(n^2)
-
步驟
（1）比較相鄰的元素。如果第一個比第二個大氯葬，就交換他們兩個挡篓。
（2）對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對帚称。在這一點官研，最后的元素應(yīng)該會是最大的數(shù)。
（3）針對所有的元素重復(fù)以上的步驟世杀，除了最后一個阀参。
（4）持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較瞻坝。
-
示例
冒泡排序上圖為一輪排序蛛壳，可見一輪排序后，最大的元素93會"浮"到頂端所刀，下一輪排序則對（26,54,17,77,31,44,55,20）進行衙荐，以此重復(fù)，直到?jīng)]有元素
-
Python代碼
def bubble_sort(data_list):#冒泡排序法 length = len(data_list) exchanges = True while length > 0 and exchanges: exchanges = False for i in range(length-1): if data_list[i]>data_list[i+1]: exchanges = True #python中可直接交換兩個變量,而不需引入臨時變量temp來交換 data_list[i],data_list[i+1] = data_list[i+1],data_list[i] length-=1 #一輪排序后浮创，已放置好的那個元素不需要再參與下一輪的排序 >>>data_list = [5, 3, 7, 9, 6, 1, 10] >>>bubble_sort(data_list) >>>print(data_list) [1, 3, 5, 6, 7, 9, 10] #增加exchanges作為標(biāo)識忧吟，即如果有一趟排序中沒有產(chǎn)生交換的話，那么說明此刻數(shù)列以及變成了有序的數(shù)列斩披，如：5溜族，1讹俊，2，3煌抒，4仍劈，冒泡一次之后就變成了：1，2寡壮，3贩疙，4，5况既，已經(jīng)有序了这溅，我們沒有必要再去比較了。
4棒仍、選擇排序法
-
基本思想
每個回合都選擇出剩下的元素中最斜ァ（大）的那個，選擇的方法是首先默認第一元素是最心洹（大）的对竣，如果后面的元素比它小（大）的話榜配，那就更新當(dāng)前的最小（大）的元素值吕晌，直到找到最后蛋褥，把當(dāng)前參與排序中的第一個元素和找到的那個最小（值）所在的位置交換睛驳。以此重復(fù)排序烙心，直到排序完成。時間復(fù)雜度O(n^2)乏沸，選擇排序法是不穩(wěn)定排序算法淫茵。
-
步驟
（1）在待排序記錄A[1]~A[n]中選出最小的記錄，將它與A[1]交換
（2）在待排序記錄A[2]~A[n]中選出最小的記錄蹬跃，將它與A[2]交換
（3）以此類推匙瘪，第i趟在待排序記錄A[i]~A[n]中選出最小的記錄，將它與A[i]交換蝶缀，使有序序列不斷增長直到全部排序完畢丹喻。
-
示例
初始序列：{49 27 65 97 76 12 38} ，其中大括號內(nèi)為無序區(qū)翁都，大括號外為有序序列
第1趟：先假設(shè)第一個元素49是最小的碍论，然后不停往后比較，找到12是當(dāng)前最小的元素柄慰，則將12與49交換：12{27 65 97 76 49 38}
第2趟：在剩余元素中假設(shè)27最小的鳍悠，不停查找到最后税娜，27還是最小的，故保持27不動〔匮小：12 27{65 97 76 49 38}
第3趟：方法同上敬矩，此處是65與38交換：12 27 38{97 76 49 65}
第4趟：方法同上，此處是97與49交換：12 27 38 49{76 97 65}
第5趟：方法同上遥倦，此處是76與65交換：12 27 38 49 65{97 76}
第6趟：方法同上谤绳，此處是97與76交換：12 27 38 49 65 76 97 完成
-
Python代碼
def select_sort(data_list):#選擇排序法 length = len(data_list) for i in range(length): min_index = i #記錄最小元素的下標(biāo)（每次都是把參與排序的第一個元素先作為最小值） for j in range(i+1,length): #在i+1開始一直往后查找最小值 if data_list[j] < data_list[min_index]: min_index = j #找到了更小的值，故當(dāng)前最小元素下標(biāo)變?yōu)榱薺 if min_index != i: #min_index=i時,是不用交換的 data_list[i],data_list[min_index] = data_list[min_index],data_list[i] #每次交換袒哥，都是把找到的最小值放在參與排序元素里的第一位 >>>data_list = [5, 3, 7, 9, 6, 1, 10] >>>select_sort(data_list) >>>print(data_list) [1, 3, 5, 6, 7, 9, 10]
5缩筛、插入排序法
-
基本思想
輸入一個元素，檢查數(shù)組列表中的每個元素堡称，將其插入到一個已經(jīng)排好序的數(shù)列中的適當(dāng)位置瞎抛，使數(shù)列依然有序，當(dāng)最后一個元素放入合適位置時却紧，該數(shù)組排序完畢桐臊。
-
示例
假設(shè)用戶輸入序列為[7，3晓殊，1断凶，4，8] （目標(biāo)：判斷數(shù)字有沒有在正確的位置上巫俺，做法：與左邊的數(shù)字對比）
（1）首先從第二個數(shù)字3開始认烁，看看3有沒在正確的位置上，與7對比介汹，比7小却嗡，故交換位置，此時序列變?yōu)?/p>
[3嘹承，7窗价，1，4叹卷，8]
（2）看看第三個數(shù)字1是否在正確的位置上撼港，與7比較，比7小豪娜，故與7交換餐胀，再與左邊的3比較，比3小瘤载，再次與3交換否灾，此時序列變?yōu)閇1，3鸣奔，7墨技，4惩阶，8]
（3）看看第四個數(shù)字4是否在正確的位置上，與7比較扣汪，比7小断楷，故與7交換，再與左邊的3比較崭别，比3大冬筒，不用交換了，此時序列變?yōu)閇1茅主，3舞痰，4，7诀姚，8]
（3）看看第五個數(shù)字8是否在正確的位置上响牛，與7比較，比7大赫段，不用交換了呀打，元素遍歷完畢，排序完成
-
Python代碼
def insert_sort(data_list):#插入排序法 length = len(data_list) for i in range(1,length): #從第二個元素開始尋找其“正確”位置 key = data_list[i] #設(shè)置當(dāng)前元素值為key j = i - 1 #與當(dāng)前值key的前一個元素對比 while j >= 0 and data_list[j] > key: data_list[j+1] = data_list[j] #前一個元素大于當(dāng)前值key,則將前一個元素后移一位 j-=1 data_list[j+1] = key #j+1即為當(dāng)前值key的合適位置 return data_list >>>data_list = [5, 3, 7, 9, 6, 1, 10] >>>print(insert_sort(data_list)) [1, 3, 5, 6, 7, 9, 10]
6糯笙、歸并排序法(合并排序法)
-
基本思想
典型的是二路合并排序贬丛，將原始數(shù)據(jù)集分成兩部分(不一定能夠均分)，分別對它們進行排序给涕，然后將排序后的子數(shù)據(jù)集進行合并瘫寝，這是典型的分治法策略（分治思想是將每個問題分解成個個小問題，將每個小問題解決稠炬，然后合并）。時間復(fù)雜度O(nlogn)
-
步驟
（1）：將n個元素分成兩個含n/2元素的子序列
（2）：用歸并排序法將兩個子序列遞歸排序（最后可以將整個原序列分解成n個子序列）
（3）：合并兩個已排序好的子序列（合并的過程是將兩個子序列排序咪啡，合成一個有序的序列）
-
示例
假設(shè)輸入序列為[54, 26, 93, 17, 77, 31, 44, 55, 20]
（1）首先將序列拆分成二等分：[54,26,93,17]和[77, 31, 44, 55, 20]
（2）對左邊的序列[54,26,93,17]繼續(xù)執(zhí)行拆分首启，分為[54,26]和[93,17]，再遞歸拆分撤摸，分為[54]和[26]毅桃，此時序列中均只剩一個元素了，則進行合并比較操作准夷，54>26钥飞，result=[26,54]
（3）再對右邊序列[93,17]拆分，分為[93]和[17]衫嵌，序列中均只剩一個元素了读宙，故進行合并比較操作，93>17楔绞，result=[26,54]
（4）對（2）（3）步得到的序列[26,54]和[17,93]遞歸合并排序（在此講述一次合并步驟结闸，其他不再贅述）唇兑，首先i=0，j=0桦锄，26>17扎附，故在result=[ ]中加入17，此時移動指針變?yōu)閖结耀，故j+=1留夜；再繼續(xù)比較，26<93图甜，在result中加入26碍粥，則result=[17,26]，這時移動指針變?yōu)閕了具则，故i+=1即纲；再繼續(xù)比較54和93，54<93博肋，在result中加入54低斋，則result=[17,26,54]；此時左邊序列已遍歷完匪凡，故可直接將右邊序列元素加到result后面了膊畴，即result += right[j:]，得到result=[17,26,54,93]
（5）{77, 31, 44, 55, 20}操作也同理病游，得到[20,31,44,55,77]
（6）最后對[17,26,54,93]與[20,31,44,55,77]進行合并排序即可
歸并排序?
歸并排序2 -
Python代碼
def merge_sort(data_lists): # 歸并排序 if len(data_lists) <= 1:#只有一個元素時,不進行切分,而是返回列表唇跨，緊接著開始第一次merge return data_lists num = int(len(data_lists) / 2)#每次都是二等分 left = merge_sort(data_lists[:num])#遞歸執(zhí)行:拆分成二等份步驟 right = merge_sort(data_lists[num:]) return merge(left, right) def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 #退出循環(huán)時，表left或者right有一個已經(jīng)遍歷完畢衬衬。假設(shè)right遍歷完畢买猖，則是將剩余的left里的值全部添加到result中，此時right[j:]為[]的 result += left[i:] result += right[j:] return result >>>a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>>print(merge_sort(a_list)) [17, 20, 26, 31, 44, 54, 55, 77, 93]
7滋尉、希爾排序法
-
基本思想
是插入排序的一種玉控。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本狮惜。其先取一個小于n的整數(shù)d1作為第一個增量高诺，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個組中碾篡。先在各組內(nèi)進行直接插入排序虱而；然后，取第二個增量d2<d1重復(fù)上述的分組和排序开泽，直至所取的增量dt=1（dt<dt-1<...<d2<d1）即所有記錄放在同一組中進行直接插入排序為止牡拇。（實質(zhì)是分組插入）
-
示例
假設(shè)用戶輸入[49,38,65,97,76,13,27,49,55,04]，
（1）第一趟初始增量d1=10/2=5，即將10個待排記錄增量分為5個子序列诅迷，分別為[49,13]佩番，[38,27]，[65,49]罢杉，[97,55]趟畏，[76,04]
（2）對上述5個分組分別進行插入排序（具體插入排序步驟看上面講述），每次排序時插回原序列對應(yīng)的位置中滩租，如[49,13]赋秀，開始時49下標(biāo)為0，13下標(biāo)為5律想，而13<39猎莲，故排序后，下標(biāo)0的位置是13技即，而49移動到原來13所在的下標(biāo)位置5著洼，其他同理，第一趟排序后序列變?yōu)閇13,27,49,55,04,49,38,65,97,76]
（3）縮小增量d2=5/2=2而叼，即將第一趟排序后的序列分為2組身笤，分別為[13,49,04,38,97]，[27,55,49,65,76]
（4）對上述2個分組分別進行插入排序（具體插入排序步驟看上面講述）葵陵，第2趟排序后序列變?yōu)閇04,27,13,49,38,55,49,65,97,76]
（5）縮小增量d3=2/2=1液荸，即將第二趟排序后的序列分為1組，[04,27,13,49,38,55,49,65,97,76]
（6）對上述分組[04,27,13,49,38,55,49,65,97,76]進行插入排序脱篙，第3趟排序后序列變?yōu)閇04,13,27,38,49,49,55,65,76,97]
希爾排序 -
Python代碼
def shell_sort(a_list):#希爾排序 sublist_count = len(a_list) // 2 #增量因子d while sublist_count > 0: for start_position in range(sublist_count): gap_insertion_sort(a_list, start_position, sublist_count) #按照d分組后得到的值進行插入排序 print("增量因子為：", sublist_count, " 排序后列表為:", a_list) sublist_count = sublist_count // 2 #增量因子d=1時,完成所有排序 def gap_insertion_sort(a_list, start, gap):#插入排序法的步驟 for i in range(start + gap, len(a_list), gap): #從第二個增量后的值start+gap開始進行插入排序 current_value = a_list[i] position = i while position >= gap and a_list[position - gap] > current_value: a_list[position] = a_list[position - gap] position = position - gap a_list[position] = current_value >>>a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>>shell_sort(a_list) print(a_list) 增量因子為： 4 排序后列表為: [20, 26, 44, 17, 54, 31, 93, 55, 77] 增量因子為： 2 排序后列表為: [20, 17, 44, 26, 54, 31, 77, 55, 93] 增量因子為： 1 排序后列表為: [17, 20, 26, 31, 44, 54, 55, 77, 93] [17, 20, 26, 31, 44, 54, 55, 77, 93]
