690
排序算法總結-python實現
最近在複習軟考，把看到的排序算法整理了一下，之所以用python寫，是因為python寫起來簡單....好吧，後來寫的時候發現有些地方用C寫還方便些。python雖然簡潔，但用起來效率感覺還是有些低，不過這不是重點啦。。。
1.代碼與說明
# -*- coding: utf-8 -*-
def bubbleSort(Data):
'''冒泡排序： 時間複雜度最好O(n)，平均O(n*n)，最壞O(n*n)，輔助空間 O(1)，算法穩定
n個數，每次從第一個數開始和相鄰的數比較，將大的冒泡到後麵去。第一趟將最大的冒泡到最後，
然後第二次隻需比較0~n-1，將其中最大的冒泡到n-1，依次下去...總共進行n-1趟排序即可
'''
if Data:
for i in range(len(Data)):
for j in range(len(Data)-i-1):
if Data[j]>Data[j+1]:
Data[j],Data[j+1]=Data[j+1],Data[j]
return Data
def quickSort(Data,low,high):
'''快速排序：O(n*logn),O(n*logn),O(n*n),O(n*logn),不穩定
冒泡的改進，被認為是當前最優秀的內部排序算法（當然這也不是絕對的，還要看具體情況）。實現基於分治法：分解-解決-合並。
基本思想：
1.從數列中取出一個基數，
2.將數列中比他大的放在右邊，小的在左邊。
3.兩邊區間重複2，直到各區間隻有一個數。
整個算法中的基數就是個坑，跳來跳去，總之比他小始終放一邊，大的放另一邊就行
參考：https://blog.csdn.net/morewindows/article/details/6684558
'''
if low < high:
left,right,base=low,high,Data[low]
while left <right:
#從後往前找比base小的數
while left <right and Data[right] >=base:
right-=1
if left < right:
Data[left]=Data[right]
#left+=1 這裏直接+1更快，因為Data[left]必然小於base，下次循環不用算
#從前往後找比base大的數
while left <right and Data[left] < base:
left+=1
if left <right:
Data[right]=Data[left]
#right-=1
#left=right時一趟循環終止，base填回坑裏去
Data[left]=base
quickSort(Data,low,left-1) #遞歸左邊
quickSort(Data,left+1,high) #遞歸右邊
def insertSort(Data):
'''插入排序： 時間複雜度最好O(n)，平均O(n*n)，最壞O(n*n)，輔助空間 O(1)，算法穩定
如果Data不為空則開始比較。Data[0]~Data[j]是排好的序列L1，key是未排待插入數據
如果key小於L1的最大值則將進行插入操作，while循環找到比key小的index並將key插入
在index後麵。while循環用來尋找插入位置並將比key大的數後移，如果key本身比L1的
最大值還大則無需插入，直接for循環比較下一個
'''
if Data:
for i in range(1,len(Data)):
key,j = Data[i],i-1
while j>=0 and Data[j] > key:
Data[j+1]=Data[j]
j-=1
Data[j+1]=key
return Data
def selectSort(Data):
'''選擇排序： 時間複雜度最好O(n*n)，平均O(n*n)，最壞O(n*n)，輔助空間 O(1)，算法不穩定
n個數，每一趟從待排序列L2中選擇最大（或最小）數順序放在已排好序列L1後麵（或前麵）
總共經過n-1趟可排好，與插入排序相比，都是將數據分為已排和未排序列並將未排元素整理
到已排序列中，不同的是插入排序在未排序列中按序整理，選排則是按大小選擇整理。
'''
if Data:
for i in range(len(Data)-1):
minnum=i
for j in range(i+1,len(Data)):#在L2中尋找最小值
if Data[j]<Data[minnum]:
minnum=j
if minnum != i:#如果找到直接交換，插入在L1後麵
Data[i],Data[minnum]=Data[minnum],Data[i]
return Data
def shellSort(Data):
'''希爾排序: 時間複雜度最好未知，平均O(pow(n,1.25)，最壞未知，輔助空間 O(1)，不穩定
插入排序的改進，將數據分組，每組m個（m叫步長）每次對每組的第i個元素排序，
然後再分組，再排序，直到步長為1.至於分組的方法需要理論推導，此處每次步長都取n/2減半
更好的步長選擇方法見wiki:https://zh.wikipedia.org/wiki/希爾排序
其他實現方法：https://blog.csdn.net/morewindows/article/details/6668714
'''
n=len(Data)
if n > 1:
gap=n/2
while gap > 0:
for i in range(gap):#按步長插入排序
for j in range(i+gap,n,gap):
if Data[j] < Data[j-gap]:
key = Data[j]
k=j-gap
while k >=0 and Data[k] > key:
Data[k+gap]=Data[k]
k-=gap
Data[k+gap]=key
gap/=2
return Data
if __name__ =="__main__":
Data=[3,5,1,56,3,7,34,21,8]
print Data
#insertSort(Data)
#bubbleSort(Data)
#selectSort(Data)
#shellSort(Data)
quickSort(Data,0,len(Data)-1)
print Data
2.python內置排序
3.瞎扯
1.內部排序是指待排序列完全存放在內存中進行的排序，適合不太大的序列。包括
插入排序（直接插入排序）
快速排序
選擇排序（簡單選擇排序）
冒泡排序
希爾排序
堆排序
歸並排序
2.外部排序指能處理大量數據的排序算法，數據不能一次裝入內存，通常要借助外存儲器。常采用排序-歸並策略，比如外歸並排序。詳情參考wiki：https://zh.wikipedia.org/wiki/外排序
3.python中沒有自增和自減運算，這在寫代碼的時候異常不方便。當然咯，這也與python的設計目標有關係。python的設計哲學是優雅，明確、簡單。他們可能認為這樣不太優雅，不利於代碼的可讀性，譬如js也不推薦使用++和--。另外一個原因，那就是python不提供像C那樣直接操作內存的功能。當執行a+=1時，C會直接修改a在內存中的值，而python則會在內存中新建一個整型變量（也不完全這樣，有些小數據python會複用，見下麵第4點），然後讓a指向它。所以如果要執行a++，C語言中a還是那個a，而python中的a已經不是原來的a了，這樣就亂套了！
說到這裏，再扯一下python中的可變對象和不可變對象。python中所有對象都是值的引用。不可變指的是值不可變。要修改變量的值就要在內存中新建一個值並讓變量指向它，原來的如果不用就會被GC回收。可變對象不需要在其他地方申請內存，直接在自己後麵申請/釋放空間即可，原地址不變。
4.對於小數值整型對象，比如1~100，python虛擬機在啟動時會先在內存中生成好，放在緩衝區以便於快速調用。看下麵的例子：
開始a，b為100，a is b是True，說明a，b指向內存中同一個對象，後麵值變大了，a=100000時python會在內存中新建一個對象，b=100000也會新建一個對象，所以a，b指向不同對象，故為False。id(a)是查看a的地址。
5.有關for循環，實質上是一個遍曆，for i in range(0,10),range（）會生成一個0到9的list讓i遍曆。這樣就有一個缺陷：i在循環前每一步的值是確定的，不能動態改變。而在C語言中，for(int i=n/2,i>0,i=i/2)，i是隨著循環每次都會改變的。不過事實上，i的值在循環前也是可以推算出來的，因此肯定是可以用python的for循環代替C的for（int i=n/2,i>0,i=i/2),隻不過LZ還沒想到，誰知道還麻煩說一聲，哈哈！
最後更新：2017-04-03 12:55:13