總結(jié)交換排序一 冒泡排序二 快速排序選擇排序一 直接選擇排序二 堆排序插入排序歸并排序計數(shù)排序基數(shù)排序
穩(wěn)定排序：冒泡排序，插入排序，歸并排序，計數(shù)排序，基數(shù)排序 不穩(wěn)定排序：選擇排序，快速排序，堆排序
效率上，基于比較的方法中快速排序是最快的方法，平均時間復雜度為O(nlogn)，而不基于比較的基數(shù)排序的時間復雜度是O(n)，雖然它看起來更快，實際上快速排序可以適應更多隨機化數(shù)據(jù)，且占的內(nèi)存低于基數(shù)排序，所以快速排序更流行。
主要思路：它對相鄰的兩個數(shù)進行比較，如果發(fā)現(xiàn)它們的大小與排序要求相反時，就將它們互換，達到將較小（大）的數(shù)冒出來的效果
特點：穩(wěn)定排序（從例子可以看出，在排序的過程中不會改變兩個重復數(shù)字的順序），不占用額外的內(nèi)存
代碼：
def BubbleSort(alist): for i in range(len(alist)): for j in range(len(alist) - 1, i, -1): if alist[j] < alist[j - 1]: alist[j], alist[j - 1] = alist[j - 1], alist[j] return alist主要思路：
首先選擇一個基準元素（一般選擇第一個或最后一個元素）
找到基準位置在其排好序后的正確位置
以基準元素的正確位置為分割線將原數(shù)組分為兩部分，然后以相同方法進行排序直到所有元素排序完成
那么根據(jù)上述思路，快速排序的主體代碼如下：
def QuickSort(alist): if len(alist) <= 1: return alist # 如果沒有元素或只有一個元素，直接返回 PRivot = getPartition(alist) # 得到基準元素索引 left = QuickSort(alist[:privot]) # 根據(jù)基準元素索引劃分，其左邊的元素繼續(xù)尋找基準元素 right = QuickSort(alist[privot + 1:]) # 根據(jù)基準元素索引劃分，其右邊的元素繼續(xù)尋找基準元素現(xiàn)在問題就是如何得到基準元素的正確位置，也就是如何實現(xiàn)getPartition函數(shù)。思路如下：以兩個索引i，j分別從數(shù)組的兩邊向中間搜索，即i = 0, j = len(input_array) - 1，i索引的目的是尋找大于基準元素的元素，j的目的是尋找小于基準元素的元素，每當i或j找到自己的目標則交換i，j的位置直到i == j
特點：不穩(wěn)定排序（從上面的例子就能看到，在找到基準元素位置的過程中，后面一個1最終在前一個1的前面），不需要額外的內(nèi)存（不考慮遞歸的棧內(nèi)存）
代碼：
def QuickSort(alist): """ 分為3步： 1. 找到當前基準元素的索引 2. 計算基準元素左側(cè)元素的索引 3. 計算基準元素右側(cè)元素的索引 :param alist: :return: """ if len(alist) <= 1: return alist # 如果沒有元素或只有一個元素，直接返回 privot = getPartition(alist) # 得到基準元素索引 left = QuickSort(alist[:privot]) # 根據(jù)基準元素索引劃分，其左邊的元素繼續(xù)尋找基準元素 right = QuickSort(alist[privot + 1:]) # 根據(jù)基準元素索引劃分，其右邊的元素繼續(xù)尋找基準元素 return left + [alist[privot]] + right # 返回排序后的結(jié)果def getPartition(alist): """ 得到基準元素索引 :param alist: :return: """ privotKey = alist[0] # 以第一個元素作為基準點 i = 0 # 尋找小于基準點的元素 j = len(alist) - 1 # 尋找大于基準點的元素 while(i < j): while(alist[j] >= privotKey and i < j): j -= 1 # j從右向左走，直到它小于基準點 alist[i], alist[j] = alist[j], alist[i] # 交換i, j元素 while(alist[i] <= privotKey and i < j): i += 1 # i從左向右走，直到它大于基準點 alist[i], alist[j] = alist[j], alist[i] # 交換i, j元素 return i主要思路：每次記錄下未排序中的元素的最小（大）元素的索引，然后和已排序的數(shù)組的后面的元素交換
特點：不穩(wěn)定排序（從上面的例子看，第一個5到了第二個5的后面），不需要額外的內(nèi)存
代碼：
def SelectionSort(alist): for i in range(len(alist)): min_index = i for j in range(i + 1, len(alist)): if alist[j] < alist[min_index]: min_index = j alist[i], alist[min_index] = alist[min_index], alist[i] return alist主要思路：首先通過下濾構(gòu)造最大（小）堆，然后交換根節(jié)點和最后一個元素，對前n - 1重新建堆（只需要將新的根節(jié)點進行一次下濾即可），直到所有元素排序完成。
考慮堆是一顆完全二叉樹，如果我們用數(shù)組存儲每個結(jié)點的值，那么假設父節(jié)點的索引為i，其左兒子的索引為2 * i + 1，右兒子的索引為 2 * i + 2。假設構(gòu)建最小堆，在下濾過程中，父節(jié)點需要和較小的兒子比較，如果它的值大于兒子的值，則需要將兒子的值上移，它則繼續(xù)和接下來的兒子比較直到它的值大于兒子的值
特點：不穩(wěn)定排序（上面的例子看得到，第一個5到第二個5后面了），不需要額外的內(nèi)存
代碼：
def HeapSort(alist): alist = buildHeap(alist) for i in range(len(alist) - 1, -1, -1): alist[0], alist[i] = alist[i], alist[0] percDown(alist, 0, i) return alistdef buildHeap(alist): """ 構(gòu)建最小堆 """ # 從最后一個有子結(jié)點的結(jié)點開始下濾 for i in range(int(len(alist) / 2) - 1, -1, -1): percDown(alist, i, len(alist)) return alistdef percDown(alist, root, n): len_list = len(alist) father = root child = root * 2 + 1 while child < n: if child + 1 < n and alist[child] > alist[child + 1]: # 找出較小的子節(jié)點 child += 1 if alist[father] > alist[child]: # 如果父節(jié)點大于子節(jié)點則交換 alist[father], alist[child] = alist[child], alist[father] else: break # 如果父節(jié)點小于子節(jié)點則直接退出 father = child child = father * 2 + 1 return alist主要思路：對每一個新的元素，都將其插入到已排序好的有序表中，在插入過程中，其后面的元素均向后移動一格
特點：穩(wěn)定排序，不需要額外內(nèi)存
代碼：
def InsertionSort(alist): for i in range(1, len(alist)): # 保存當前要插入的元素，并騰出當前空格 current_index = i current_value = alist[i] # 和前面的元素比較 for j in range(i - 1, 0, -1): # 如果前面的元素比它大，則將前面的元素向右移一格 if alist[j] > current_value: alist[j + 1] = alist[j] current_index = j else: break # 將當前元素插進空格 alist[current_index] = current_value return alist主要思路：歸并排序主要利用分治的思想，將待排序的數(shù)組分為兩部分，如果左邊部分已經(jīng)排序好，右邊部分也排序好，那么只需將這兩部分再按照順序組合在一起就可以了
特點： 穩(wěn)定排序，需要額外的內(nèi)存（合并操作的時候）
代碼：
def MergeSort(alist): if len(alist) <= 1: return alist middle = int(len(alist) / 2) left = MergeSort(alist[:middle]) right = MergeSort(alist[middle:]) return merge(left, right)def merge(left, right): left_index = 0 right_index = 0 res = [] while left_index < len(left) and right_index < len(right): if left[left_index] < right[right_index]: res.append(left[left_index]) left_index += 1 else: res.append((right[right_index])) right_index += 1 if left_index < len(left): res += left[left_index:] if right_index < len(right): res += right[right_index:] return res主要思路：非基于比較的排序算法（因為數(shù)組下標索引默認是有順序的，所以只要將數(shù)字對應放進去就會有順序）。對每一個輸入元素x，確定出小于x的元素個數(shù)（即它的位置），然后放到輸出數(shù)組中。在最后遍歷的時候一定要從后向前遍歷，否則排序?qū)⒉环€(wěn)定。
特點：穩(wěn)定排序，需要額外的內(nèi)存
代碼：
def CountingSort(alist, k): temp = [0 for _ in range(k + 1)] # 存儲alist中的每個元素的位置 res = [0 for _ in alist] # 保存排序后的結(jié)果 for i in alist: # temp[i]中存放了值為i的元素的個數(shù) temp[i] += 1 for t in range(1, len(temp)): # temp[i]中存放的是小于等于i元素的數(shù)字個數(shù) temp[t] += temp[t - 1] # 把輸入數(shù)組中的元素放在輸出數(shù)組中對應的位置上 for i in range(len(alist) - 1, -1, -1): # 從后向前輸出，保證重復元素按原順序輸出 res[temp[alist[i]] - 1] = alist[i] # temp[alist[i]]代表alist的第i個元素的位置 temp[alist[i]] -= 1 # 確保當遇到重復的數(shù)字時，輸出相應的位置 return res主要思路：基數(shù)排序分別從每一位開始排序（先從個位，然后十位，百位 …），比如12， 34， 7，首先按照個位排序得到12， 34， 7，然后按照十位排序（7的十位為0），得到7， 12， 34。它對于每一位的排序就是使用計數(shù)排序，因為每一位的范圍只在0-9，且計數(shù)排序是穩(wěn)定排序，所以基數(shù)排序也是穩(wěn)定排序
特點：穩(wěn)定排序， 需要額外的內(nèi)存（因為計數(shù)排序就需要額外的內(nèi)存）
代碼：
def RadixSort(alist, d): for i in range(1, d + 1): alist = CountingSort(alist, 9, i) # 每次以第i位排序，因為計數(shù)排序是穩(wěn)定的，所以可以多次排序 return alistdef CountingSort(alist, k, d): temp = [0] * (k + 1) res = [0] * len(alist) for a in alist: a = getBitData(a, d) # 得到第d位數(shù)字 temp[a] += 1 for i in range(1, len(temp)): temp[i] += temp[i - 1] for i in range(len(alist) - 1, -1, -1): a = getBitData(alist[i], d) res[temp[a] - 1] = alist[i] temp[a] -= 1 return resdef getBitData(e, d): """ 得到第d位數(shù)字 :param e: :param d: :return: """ res = e for _ in range(d): res = e % 10 e //= 10 return res新聞熱點
疑難解答
