冒泡排序
冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，走訪數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成，這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，
作為最簡單的排序演算法之一，冒泡排序給我的感覺就像 Abandon 在單詞書里出現的感覺一樣，每次都在第一頁第一位，所以最熟悉，冒泡排序還有一種優化演算法，就是立一個 flag，當在一趟序列遍歷中元素沒有發生交換，則證明該序列已經有序，但這種改進對于提升性能來說并沒有什么太大作用，
- 演算法步驟：
i.比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
ii.對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數，
iii.針對所有的元素重復以上的步驟，除了最后一個，
iv.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
def bubbleSort(arr):
leng=len(arr)
while leng-1>0:
i=1
while i<=leng-1 :
if(arr[i]<arr[i-1]):
arr[i],arr[i-1]=arr[i-1],arr[i]
i+=1
leng-=1
return arr
arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
bubbleSort(arr)
選擇排序
選擇排序是一種簡單直觀的排序演算法，無論什么資料進去都是 O(n2) 的時間復雜度，所以用到它的時候，資料規模越小越好，唯一的好處可能就是不占用額外的記憶體空間了吧，
- 演算法步驟：
i.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
ii.再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，
iii.重復第二步，直到所有元素均排序完畢，
def selectionSort(arr):
leng=len(arr)
j=0
while j<leng:
min1=arr[j]
i=j
while i<leng:
if(arr[i]<min1):
min1,arr[i]=arr[i],min1
i+=1
arr[j]=min1
j+=1
return arr
arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
selectionSort(arr)
插入排序
插入排序的代碼實作雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂，插入排序是一種最簡單直觀的排序演算法，它的作業原理是通過構建有序序列，對于未排序資料，在已排序序列中從后向前掃描，找到相應位置并插入，
插入排序和冒泡排序一樣，也有一種優化演算法，叫做拆半插入，
- 演算法步驟：
i.將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列，
ii.從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置，（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面，）
def insertionSort(arr):
leng=len(arr)
j=1
d=min(arr)
while j<leng:
a=arr.pop(j)
i=j-1
f=0
if(a==d):
arr.insert(0,a)
f=1
else:
while i>=0:
if(arr[i]<a):
arr.insert(i+1,a)
f=1
break
i-=1
if f==0:
arr.insert(j,a)
else:
f=0
j+=1
return arr
arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
insertionSort(arr)
希爾排序
希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序演算法，
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序，
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
1.插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率；
2.但插入排序一般來說是低效的，因為插入排序每次只能將資料移動一位，
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序，
- 演算法步驟：
i.選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
ii.按增量序列個數 k，對序列進行 k 趟排序；
iii.每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序，僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度，
def shellSort(arr):
i=0
leng=len(arr)
a=leng//2
while a>=1:
c=i
while c<a:
d=c
sd=[]
while d<leng:
sd.append(arr[d])
d+=a
leng1=len(sd)
j=1
d1=min(sd)
while j<leng1:
a1=sd.pop(j)
i1=j-1
f=0
if(a1==d1):
sd.insert(0,a1)
f=1
else:
while i1>=0:
if(sd[i1]<a1):
sd.insert(i1+1,a1)
f=1
break
i1-=1
if f==0:
sd.insert(j,a1)
else:
f=0
j+=1
d=c
r=0
while d<leng:
arr[d]=sd[r]
d+=a
r+=1
c+=1
a=a//2
return arr
arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
shellSort(arr)
歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，
作為一種典型的分而治之思想的演算法應用，歸并排序的實作由兩種方法：
1.自上而下的遞回（所有遞回的方法都可以用迭代重寫，所以就有了第 2 種方法）；
2.自下而上的迭代，
和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度，代價是需要額外的記憶體空間，
- 演算法步驟：
i.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
ii.設定兩個指標，最初位置分別為兩個已經排序序列的起始位置；
iii.比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置；
iv.重復步驟 3 直到某一指標達到序列尾；
v.將另一序列剩下的所有元素直接復制到合并序列尾，
def mergeSort(arr):
ff=len(arr)
if (ff <= 1):
return arr
a = int(len(arr)/2)
left = mergeSort(arr[:a])
right = mergeSort(arr[a:])
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
h, l = 0, 0
result = []
while l < len(left) and h < len(right):
if (left[l] < right[h]):
result.append(left[l])
l += 1
else:
result.append(right[h])
h += 1
result += left[l:]
result += right[h:]
return result
arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
print(mergeSort(arr))
本文僅供參考，如有錯誤，敬請指正，
本文首發于python黑洞網，博客園同步更新
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/202428.html
標籤：其他