排序
排序是計算機內經常進行的一種操作，其目的是將一組”無序”的記錄序列調整為”有序”的記錄序列。分內部排序和外部排序。若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。反之，若參加排序的記錄數量很大，整個序列的排序過程不可能完全在內存中完成，需要訪問外存，則稱此類排序問題為外部排序。內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。
看圖使理解更清晰深刻：
假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
常見排序算法
快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩定的排序算法
本文將用Python實現冒泡排序、插入排序、希爾排序、快速排序、直接選擇排序、堆排序、歸并排序、基數排序這八大排序算法。
1. 冒泡排序（Bubble Sort）
算法原理：
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪后a[1]、a[2]、……a[n]就以升序排列了。降序排列與升序排列相類似，若a[1]小于a[2]則交換兩者的值，否則不變，后面以此類推。 總的來講，每一輪排序后最大（或最小）的數將移動到數據序列的最后，理論上總共要進行n(n-1）/2次交換。
優點：穩定；
缺點：慢，每次只能移動相鄰兩個數據。
python代碼實現：
|
1
|
|
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python實現八大排序算法'''lst1 = [2,5435,67,445,34,4,34]def bubble_sort_basic(lst1): lstlen = len(lst1);i = 0 while i < lstlen: for j in range(1,lstlen): if lst1[j-1] > lst1[j]: #對比相鄰兩個元素的大小，小的元素上浮 lst1[j],lst1[j-1] = lst1[j-1],lst1[j] i += 1 print 'sorted{}: {}'.format(i, lst1) print '-------------------------------' return lst1bubble_sort_basic(lst1) |
冒泡排序算法的改進
對于全員無序或者沒有重復元素的序列，上述算法在同一思路上是沒有改進余地的，但是如果一個序列中存在重復元素或者部分元素是有序的呢，這種情況下必然會存在不必要的重復排序，那么我們可以在排序過程中加入一標志性變量change，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程，改進后示例代碼如下：
|
1
|
|
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
lst2 = [2,5435,67,445,34,4,34]def bubble_sort_improve(lst2): lstlen = len(lst2) i = 1;times = 0 while i > 0: times += 1 change = 0 for j in range(1,lstlen): if lst2[j-1] > lst2[j]: #使用標記記錄本輪排序中是否有數據交換 change = j lst2[j],lst2[j-1] = lst2[j-1],lst2[j] print 'sorted{}: {}'.format(times,lst2) #將數據交換標記作為循環條件，決定是否繼續進行排序 i = change return lst2bubble_sort_improve(lst2) |
兩種情況下運行截圖如下：
由上圖可以看出，對于部分元素為有序排列的序列，優化后的算法減少了兩輪排序。
2.選擇排序（Selection Sort）
算法原理：
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
優點：移動數據的次數已知（n-1次）；
缺點：比較次數多，不穩定。
python代碼實現：
|
1
|
|
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
# -*- coding: UTF-8 -*-'''Created on 2017年8月31日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def selection_sort(lst): lstlen = len(lst) for i in range(0,lstlen): min = i for j in range(i+1,lstlen): #從 i+1開始循環遍歷尋找最小的索引 if lst[min] > lst[j]: min = j lst[min],lst[i] = lst[i],lst[min] #一層遍歷結束后將最小值賦給外層索引i所指的位置，將i的值賦給最小值索引 print('The {} sorted: {}'.format(i+1,lst)) return lstsorted = selection_sort(lst)print('The sorted result is: {}'.format(sorted)) |
運行結果截圖：
3. 插入排序
算法原理：
已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合并成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大于a[2]，則繼續跳過，直到b[1]小于a數組中某一數據a[x]，則將a[x]~a[n]分別向后移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越多，插入點后的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。
算法復雜度
如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序算法的時間復雜度為O(n^2）。因而，插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。
python代碼實現：
|
1
|
|
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
# -*- coding: UTF-8 -*-'''Created on 2017年8月31日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def insert_sort(lst): count = len(lst) for i in range(1, count): key = lst[i] j = i - 1 while j >= 0: if lst[j] > key: lst[j + 1] = lst[j] lst[j] = key j -= 1 print('The {} sorted: {}'.format(i,lst)) return lstsorted = insert_sort(lst)print('The sorted result is: {}'.format(sorted)) |
運行結果截圖：
由排序過程可知，每次往已經排好序的序列中插入一個元素，然后排序，下次再插入一個元素排序。。。直到所有元素都插入，排序結束
4. 希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。
算法原理
算法核心為分組（按步長）、組內插入排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最后一組以次類推，在各組內用插入排序，然后取d'<d，重復上述操作，直到d=1。
python代碼實現：
|
1
|
|
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python實現八大排序算法'''lst = [65,568,9,23,4,34,65,8,6,9]def shell_sort(lists): print 'orginal list is {}'.format(lst) count = len(lists) step = 2 times = 0 group = int(count/step) while group > 0: for i in range(0, group): times += 1 j = i + group while j < count: k = j - group key = lists[j] while k >= 0: if lists[k] > key: lists[k + group] = lists[k] lists[k] = key k -= group j += group print 'The {} sorted: {}'.format(times,lists) group = int(group/step) print 'The final result is: {}'.format(lists) return listsshell_sort(lst) |
運行測試結果截圖：
過程分析：
第一步：
1-5：將序列分成了5組（group = int(count/step)）,如下圖，一列為一組：
然后各組內進行插入排序，經過5（5組*1次）次組內插入排序得到了序列：
The 1-5 sorted：[34, 65, 8, 6, 4, 65, 568, 9, 23, 9]
第二步：
6666-7777：將序列分成了2組（group = int(group/step)）,如下圖，一列為一組：
然后各組內進行插入排序，經過8（2組*4次）次組內插入排序得到了序列：
The 6-7 sorted: [4, 6, 8, 9, 23, 9, 34, 65, 568, 65]
第三步：
888888888：對上一個排序結果得到的完整序列進行插入排序：
[4, 6, 8, 9, 23, 9, 34, 65, 568, 65]
經過9（1組*10 -1）次插入排序后：
The final result is: [4, 6, 8, 9, 9, 23, 34, 65, 65, 568]
希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于增量因子序列的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩定的排序方法
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/lockey23/article/details/77760746
