八大排序演算法python實現合輯

1.冒泡排序

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

步驟：

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

3. 針對所有的元素重複以上的步驟，除了最後一個。

4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

代碼實現：

# -*- coding:utf-8 -*-def bubble_sort(list): length=len(list) for index in range(length): for i in range(1,length-index): if list[i-1]<list[i]: list[i],list[i-1]=list[i-1],list[i] return list#一下為測試其正確性：list=[10,23,1,53,654,54,16,646,65,3155,546,31]print bubble_sort(list)

2.選擇排序

從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

# -*- coding:utf-8 -*-def select_sort(list): length=len(list) for index in range(length): for i in range(index,length): if list[index]<list[i]: list[index],list[i]=list[i],list[index] return list#測試list=[10,23,1,53,654,54,16,646,65,3155,546,31]print select_sort(list)

3.插入排序

每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

步驟：

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到該位置後
6. 重複步驟2~5

代碼實現：

# -*- coding:utf-8 -*-def insert_sort(lists): # 插入排序 count = len(lists) for i in range(1, count): key = lists[i] j = i - 1 while j >= 0: if lists[j] > key: lists[j + 1] = lists[j] lists[j] = key j -= 1 return lists#測試list=[10,23,1,53,654,54,16,646,65,3155,546,31]print insert_sort(lists)

4.希爾排序

先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量

即所有記錄放在同一組中進行直接插入排序為止。

# -*- coding:utf-8 -*-def shell_sort(list): length=len(list) dist=length/2 while dist>0: for i in range(dist,length): temp=list[i] j=i while j>=dist and temp<list[j-dist]: list[j]=list[j-dist] j-=dist list[j]=temp dist/=2 return list#測試list=[10,23,1,53,654,54,16,646,65,3155,546,31]print shell_sort(list)

5.歸併排序

歸併排序，就是把兩個已經排列好的序列合併為一個序列。

代碼實現：

# -*- coding:utf-8 -*-#演算法邏輯比較簡單，以第一個list為基準，第二個向第一個插空def merge_sort(list1,list2): length_list1=len(list1) length_list2=len(list2) list3=[] j=0 for i in range(length_list1): while list2[j]<list1[i] and j<length_list2: list3.append(list2[j]) j=j+1 list3.append(list1[i]) if j<(length_list2-1): for k in range(j,length_list2): list3.append(list2[k]) return list3#測試list1=[1,3,5,10]list2=[2,4,6,8,9,11,12,13,14]print merge_sort(list1,list2)

6.快速排序

隨意選擇一個數字作為基準，比基準數字大的在右，比基準數字小的在左。# -*- coding:utf-8 -*-def kp(arr,i,j):#快排總函數 #制定從哪開始快排 if i<j: base=kpgc(arr,i,j) kp(arr,i,base) kp(arr,base+1,j)def kpgc(arr,i,j):#快排排序過程 base=arr[i] while i<j: while i<j and arr[j]>=base: j-=1 while i<j and arr[j]<base: arr[i]=arr[j] i+=1 arr[j]=arr[i] arr[i]=base return iww=[3,2,4,1,59,23,13,1,3]print wwkp(ww,0,len(ww)-1)print ww

7.堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

步驟：

1. 創建最大堆:將堆所有數據重新排序，使其成為最大堆
2. 最大堆調整:作用是保持最大堆的性質，是創建最大堆的核心子程序
3. 堆排序:移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

代碼實現：

# -*- coding:utf-8 -*-def head_sort(list): length_list = len(list) first=int(length_list/2-1) for start in range(first,-1,-1): max_heapify(list,start,length_list-1) for end in range(length_list-1,0,-1): list[end],list[0]=list[0],list[end] max_heapify(list,0,end-1) return listdef max_heapify(ary,start,end): root = start while True: child = root*2 + 1 if child > end: break if child + 1 <= end and ary[child]<ary[child+1]: child = child + 1 if ary[root]<ary[child]: ary[root],ary[child]=ary[child],ary[root] root=child else: break#測試：list=[10,23,1,53,654,54,16,646,65,3155,546,31]print head_sort(list)

8.計數排序

# -*- coding:utf-8 -*-def count_sort(list): max=min=0 for i in list: if i < min: min = i if i > max: max = i count = [0] * (max - min +1) for j in range(max-min+1): count[j]=0 for index in list: count[index-min]+=1 index=0 for a in range(max-min+1): for c in range(count[a]): list[index]=a+min index+=1 return list #測試：list=[10,23,1,53,654,54,16,646,65,3155,546,31]print count_sort(list)

本文來源於自己剛學數據結構時的筆記，文字敘述以及代碼實現思維參考了百度百科，大神@EINDEX 的專欄以及網上搜到的經驗貼，感激ing^_^