目錄
8.1 排序相關概念
8.2?插入排序
8.2.1 直接插入排序：
8.2.2 折半插入排序：
8.2.3 希爾排序：
8.3?交換排序
8.3.1 冒泡排序：
8.3.2 快速排序：
8.4?選擇排序
8.4.1 簡單選擇排序
8.4.2 堆排序
8.5?歸并排序
8.6?排序算法復雜度
8.1 排序相關概念
- 排序碼：排序的依據，也稱關鍵碼
- 排序是對線性結構的一種操作
- 排序算法的穩定性：假定在待排序的記錄序列中存在多個具有相同關鍵碼的記錄，若經過排序，這些記錄的相對次序保持不變，則稱這種排序算法穩定，否則為不穩定。
- 根據排序過程中所有記錄是否全部放在內存中，排序方法分為
? ? （1） 內排序：過程中，待排序的所有記錄全部放在內存中
? ? （2） 外排序：過程中，需要在內外存之間交換數據
- 根據排序方法是否建立在關鍵碼比較的基礎上，排序方法分為：
? ? （1） 基于比較：通過關鍵碼之間的比較和記錄的移動實現。（包括插入排序、交換排序、選擇排序和歸并排序）
? ? （2） 不基于比較：根據待排序數據的特點所采取的其他方法。（基數排序）
8.2?插入排序
8.2.1 直接插入排序：
??? 基本思路：有將數組分為有序區和無序區，初始時有序區只有一個元素，將無序區的元素一個一個插入有序區，直到所有元素都在有序區內。
# 直接插入排序
def InsertSort(R):for i in range(1,len(R)):if R[i]<R[i-1]:temp = R[i] # 取出無序區的第一個元素j = i-1 # 前面都是有序的，在有序區中找插入的位置while True:R[j+1] = R[j] # 將大于temp的元素后移，空出一個插入的位置j-=1if j<0 or R[j]<=temp:breakR[j+1] = tempreturn R
8.2.2 折半插入排序：
??? 折半插入排序和直接插入排序思路差不多，不過在將無序區元素插入有序區時用折半的方法插入。只是優化了插入的部分。
8.2.3 希爾排序：
??? 基本思路：先將整個待排序記錄序列分隔成若干個子序列，在子序列內分別進行直接插入排序，待整個序列基本有序后，再對整體記錄進行一次直接插入排序。
??? 步驟：
??? （1） 相鄰d個位置的元素分為一組，d=n/2（d是增量）
??? （2） 將排序序列分為d個組，在各組內進行直接插入排序
??? （3） 遞減d=d/2，重復第二步，直到d=0為止
希爾算法的時間復雜度難以分析，一般認為其平均時間復雜度為O(n1.58)。希爾排序的速度通常要比直接插入排序快。
希爾排序是一種不穩定的排序算法
8.3?交換排序
8.3.1 冒泡排序：
??? 基本思路：兩個元素反序時進行交換
??? 冒小泡：從后往前看，如果后面的比前面的小就交換。
若某一趟沒有出現元素交換，說明所有元素已排好序了。
# 冒泡排序
def BubbleSort(R):for i in range(len(R)-1):exchange = Falsefor j in range(len(R)-1,i,-1):if R[j]<R[j-1]:R[j],R[j-1] = R[j-1],R[j]exchange=Trueif exchange == False:return R8.3.2 快速排序：
??? 先選擇一個基準（一般是第一個元素），將待排序記錄劃分為兩部分，左側關鍵碼小于基準，右側關鍵碼大于基準，將基準值與左側最后一個值交換位置，使得基準值在中間。然后分別對左右部分重復上述過程，直到排好。
【例題】
快速排序過程可以用遞歸樹表示
#快速排序
def quickSort(lst,l,r):if r<=l:returnq = partition(A,l,r)quickSort(A,l,q-1)quickSort(A,q+1,r)def partition(A,l,r): #將元素進行隨機劃分p = randint(A[l],A[r])A[p],A[r] = A[r],A[p]i = lfor j in range(l,r-1):if A[j]<=A[r]:A[i],A[j] = A[j],A[i]i+=1A[i],A[r] = A[r],A[i]return i8.4?選擇排序
8.4.1 簡單選擇排序
??? 分為無序區和有序區，每趟在無序區中選出最小的記錄minj，將minj和有序區后一個數字交換。
??? 是一種不穩定的排序方法
# 簡單選擇排序
def SelectSort(R):for i in range(len(R)-1):minj = ifor j in range(i+1,len(R)):if R[j]<R[minj]: # 從無序區選最小元素minj = jif minj!=i:R[i],R[minj] = R[minj],R[i]8.4.2 堆排序
??? 堆是完全二叉樹
??? 堆的存儲是順序的
??? 堆的定義：大根堆，小根堆
??? 大根堆：父結點的關鍵字大于子結點的關鍵字
步驟：
（1）根據序列用廣度優先構建一個完全二叉樹，上濾（自底向上）調整為大根堆
（2）輸出堆頂元素，然后用堆尾元素代替堆頂
（3）從根節點篩選，使其形成一個堆（此時的根節點就是之前的堆尾元素）
??? 篩選：將根節點與左右孩子的較大者進行交換，一直進行到所有子樹均為堆或將調整結點交換到葉子位置。
（4）重復二三步驟（n-1次），得到有序序列
【例題】
8.5?歸并排序
基礎思路：將兩個位置相鄰的有序子序列歸并為一個有序序列
歸并要做??趟，每趟歸并時間為O(n)
#歸并排序，給列表A中下標從l到r的區間排序
def mergeSort(A,l,r):if r-l<=1:#邊界條件處理returnmid = (l+r)//2mergeSort(A,l,mid)#遞歸調用mergeSort(A,mid,r)merge(A,l,mid,r)#遞推到當前層def merge(A,l,mid,r): #合并數組A[l,m-1]和A[m,r-1]l = A[l,mid-1]r = A[mid,r-1]k = 0i = 0j = 0while k<=r-l:if l[i]<=r[j]:i +=1A[K] = l[i]else:A[K] = r[j]j+=1k+=18.6?排序算法復雜度
基于比較排序算法的平均時間復雜度不可能優于
