1.平均時間復雜度均為O(N2)的排序
1.1 插入排序
插入排序對少量元素的排序非常有效。工作機制就像打牌一樣，為了將牌插入到已排好序的牌中，需要將牌與手中的牌從右向左進行比較。
def insertionSort(alist): n=len(alist) for i in xrange(1,n): key=alist[i] j=i-1 while j>=0 and alist[j]>=key: alist[j+1]=alist[j] j-=1 alist[j+1]=key return alist
1.2 冒泡排序
冒泡排序通過重復的交換相鄰的兩個反序元素來將最大元素置于數組末尾。
def bubbleSort(alist): n=len(alist) for i in xrange(n-2,0,-1): for j in xrange(i+1): if alist[j]>alist[j+1]: alist[j],alist[j+1]=alist[j+1],alist[j] return alist
1.3 選擇排序
首先找出序列中的最大元素，與最后一個元素交換位置，然后找出次大元素，與倒數第二個元素交換位置，以此類推。
def selectionSort(alist): n=len(alist) for i in xrange(n-1,0,-1): posofMax=0 for j in xrange(1,i+1): if alist[j]>=alist[posofMax]: posofMax=j a[posofMax],a[i]=a[i],a[posofMax] return alist
1.4 希爾排序
SHELL排序通過比較相距一定間隔的元素來工作。各趟排序隨著算法的進行而減小，直到只比較相鄰元素的最后一趟為止。
使用希爾增量(ht=N/2,hk=hk+1/2)時希爾排序的最壞運行時間為Θ(N2)，使用Hibbard增量(1,3,7,...,2k-1)的希爾排序的最壞運行時間為Θ(N3/2)。
def shellSort(alist): n=len(alist)/2 while n>0: gapinsertionSort(alist,n) n=n/2 return alistdef gapinsertionSort(alist,gap): n=len(alist) for i in xrange(gap): for j in xrange(i+gap,n,gap): key=alist[j] x=j-gap while x>=0 and a[x]>=key: a[x+gap]=a[x] x-=gap a[x+gap]=key
2.平均時間復雜度均為O(NlogN)的排序
2.1 合并排序
合并排序基本的操作是合并兩個已排序的表。它是遞歸算法的一個很好的實例。合并排序需要花費將數據拷貝到臨時數組再拷貝回來這樣一些附加的工作。
def mergeSort(alist): if len(alist)>1: q=len(alist)/2 left=alist[:q] right=alist[q:] mergeSort(left) mergeSort(right) i=0 j=0 k=0 while i<len(left) and j<len(right): if left[i]<right[j]: alist[k]=left[i] i+=1 else: alist[k]=right[j] j+=1 k+=1 while i<len(left): alist[k]=left[i] i+=1 k+=1 while j<len(right): alist[k]=right[j] j+=1 k+=1 return alist
合并排序的另一種非遞歸實現
def mergeSort(alist): n=len(alist) i=1 while i<n: start=0 t=start+i-1 end=start+2*i-1 while end<n: merge(alist,start,t,end) start=end+1 t=start+i-1 end=start+2*i-1 if t<n-1: merge(alist,start,t,n-1) i=i*2 return alist def merge(alist,start,t,end): left=alist[start:t+1] right=alist[t+1:end+1] i=0 j=0 k=start while i<len(left) and j<len(right): if left[i]<right[j]: alist[k]=left[i] i+=1 else: alist[k]=right[j] j+=1 k+=1 while i<len(left): alist[k]=left[i] i+=1 k+=1 while j<len(right): alist[k]=right[j] j+=1 k+=1
2.2 堆排序
建立最大堆后將最大元素與堆最后的單元互換，堆大小縮小一，然后執行根的下濾操作找出第二大的元素。
def heapSort(alist): n=len(alist) buildMaxHeap(alist) for i in xrange(n-1,0,-1): alist[i],alist[0]=alist[0],alist[i] perDown(alist,0,i-1) return alistdef buildMaxHeap(alist): n=len(alist) for i in xrange(n/2-1,-1,-1): perDown(alist,i,n-1)def perDown(alist,start,end): left=start*2+1 right=left+1 large=start if left<=end and alist[left]>alist[start]: large=left if right<=end and alist[right]>alist[large]: large=right if large!=start: alist[large],alist[start]=alist[start],alist[large] perDown(alist,large,end)
2.3 快速排序
快速排序是在實踐中最快的已知排序算法，像合并排序一樣也是一種分治的遞歸算法。
1.如果元素個數為0或1，則返回。
2.取數組中任一元素v，稱之為樞紐元。
3.將數組分為2個不相交的部分，一部分元素小于v，另一部分大于v。
4.對兩部分分別遞歸的使用快速排序。
下圖取第一個元素為樞紐元v，leftmark從第二個元素開始，rightmark從倒數第一個元素開始。
當leftmark在rightmark左邊時，將leftmark右移，移過小于v的元素，將rightmark左移，移過大于v的元素，當leftmark，rightmark停止時，
將leftmark和rightmark元素互換，直到leftmark到rightmark右邊為止。
def quickSort(alist): n=len(alist) _quickSort(alist,0,n-1) return alistdef _quickSort(alist,s,e): if s<e: v=alist[s] i=s+1 j=e while True: while i<=j and alist[i]<v: #如果i和j遇到等于樞紐元的關鍵字，都停止 i+=1 while j>=i and alist[j]>v: j-=1 if i<j: alist[i],alist[j]=alist[j],alist[i] i+=1 j-=1 else: break alist[s],alist[j]=alist[j],alist[s] _quickSort(alist,s,j-1) _quickSort(alist,i,e)
另一種寫法
def quickSort(alist): n=len(alist) _quickSort(alist,0,n-1) return alistdef _quickSort(alist,s,e): if s<e: v=alist[e] i=s #用i將數組分為兩部分 for j in xrange(s,e): if alist[j]<=v: alist[j],alist[i]=alist[i],alist[j] i+=1 alist[e],alist[i]=alist[i],alist[e] _quickSort(alist,s,i-1) _quickSort(alist,i+1,e)
新聞熱點
疑難解答
