八大排序算法的 Python 實現

1、插入排序

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。

1. def insert_sort(lists):
2. #插入排序
3. count = len(lists)
4. for i in range(1, count):
5. key = lists[i]
6. j = i -1
7. while j >=0:
8. if lists[j]> key:
9. lists[j +1]= lists[j]
10. lists[j]= key
11. j -=1
12. return lists

2、希爾排序

希爾排序（Shell Sort）是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

1. def shell_sort(lists):
2. #希爾排序
3. count = len(lists)
4. step =2
5. group = count / step
6. while group >0:
7. for i in range(0, group):
8. j = i + group
9. while j < count:
10. k = j - group
11. key = lists[j]
12. while k >=0:
13. if lists[k]> key:
14. lists[k + group]= lists[k]
15. lists[k]= key
16. k -= group
17. j += group
18. group /= step
19. return lists

3、冒泡排序

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

1. def bubble_sort(lists):
2. #冒泡排序
3. count = len(lists)
4. for i in range(0, count):
5. for j in range(i +1, count):
6. if lists[i]> lists[j]:
7. lists[i], lists[j]= lists[j], lists[i]
8. return lists

4、快速排序

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

1. def quick_sort(lists, left, right):
2. #快速排序
3. if left >= right:
4. return lists
5. key = lists[left]
6. low = left
7. high = right
8. while left < right:
9. while left < right and lists[right]>= key:
10. right -=1
11. lists[left]= lists[right]
12. while left < right and lists[left]<= key:
13. left +=1
14. lists[right]= lists[left]
15. lists[right]= key
16. quick_sort(lists, low, left -1)
17. quick_sort(lists, left +1, high)
18. return lists

5、直接選擇排序

基本思想：第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。

1. def select_sort(lists):
2. #選擇排序
3. count = len(lists)
4. for i in range(0, count):
5. min = i
6. for j in range(i +1, count):
7. if lists[min]> lists[j]:
8. min = j
9. lists[min], lists[i]= lists[i], lists[min]
10. return lists

6、堆排序

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

1. #調整堆
2. def adjust_heap(lists, i,size):
3. lchild =2* i +1
4. rchild =2* i +2
5. max = i
6. if i <size/2:
7. if lchild <sizeand lists[lchild]> lists[max]:
8. max = lchild
9. if rchild <sizeand lists[rchild]> lists[max]:
10. max = rchild
11. if max != i:
12. lists[max], lists[i]= lists[i], lists[max]
13. adjust_heap(lists, max,size)
14. #創建堆
15. def build_heap(lists,size):
16. for i in range(0,(size/2))[::-1]:
17. adjust_heap(lists, i,size)
18. #堆排序
19. def heap_sort(lists):
20. size= len(lists)
21. build_heap(lists,size)
22. for i in range(0,size)[::-1]:
23. lists[0], lists[i]= lists[i], lists[0]
24. adjust_heap(lists,0, i)

7、歸並排序

歸並排序是建立在歸並操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。

歸並過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，並令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，並令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸並排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸並操作合並成有序的區間[s,t]。

1. def merge(left, right):
2. i, j =0,0
3. result =[]
4. while i < len(left)and j < len(right):
5. if left[i]<= right[j]:
6. result.append(left[i])
7. i +=1
8. else:
9. result.append(right[j])
10. j +=1
11. result += left[i:]
12. result += right[j:]
13. return result
14. def merge_sort(lists):
15. #歸並排序
16. if len(lists)<=1:
17. return lists
18. num = len(lists)/2
19. left = merge_sort(lists[:num])
20. right = merge_sort(lists[num:])
21. return merge(left, right)

8、基數排序

基數排序（radix sort）屬於“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。

1. import math
2. def radix_sort(lists, radix=10):
3. k =int(math.ceil(math.log(max(lists), radix)))
4. bucket =[[]for i in range(radix)]
5. for i in range(1, k+1):
6. for j in lists:
7. bucket[j/(radix**(i-1))%(radix**i)].append(j)
8. del lists[:]
9. for z in bucket:
10. lists += z
11. del z[:]
12. return lists

下面關於Python的文章您也可能喜歡，不妨看看：

Python：在指定目錄下查找滿足條件的文件  http://www.linuxidc.com/Linux/2015-08/121283.htm

Python2.7.7源碼分析  http://www.linuxidc.com/Linux/2015-08/121168.htm

無需操作系統直接運行 Python 代碼  http://www.linuxidc.com/Linux/2015-05/117357.htm

CentOS上源碼安裝Python3.4  http://www.linuxidc.com/Linux/2015-01/111870.htm

《Python核心編程 第二版》.(Wesley J. Chun ).[高清PDF中文版] http://www.linuxidc.com/Linux/2013-06/85425.htm

《Python開發技術詳解》.( 周偉,宗傑).[高清PDF掃描版+隨書視頻+代碼] http://www.linuxidc.com/Linux/2013-11/92693.htm

Python腳本獲取Linux系統信息 http://www.linuxidc.com/Linux/2013-08/88531.htm

在Ubuntu下用Python搭建桌面算法交易研究環境 http://www.linuxidc.com/Linux/2013-11/92534.htm

Python 語言的發展簡史 http://www.linuxidc.com/Linux/2014-09/107206.htm

Python 的詳細介紹：請點這裡
Python 的下載地址：請點這裡