姓名：宋子璇
學號：16020199060
轉載自：https://zhuanlan.zhihu.com/p/34854599
【嵌牛導讀】：排序算法對比
【嵌牛鼻子】：排序 Python
【嵌牛提問】：排序算法都有哪些？
【嵌牛正文】
排序大的分類可以分為兩種：內排序和外排序。在排序過程中，全部記錄存放在內存，則稱為內排序，如果排序過程中需要使用外存，則稱為外排序。下面講的排序都是屬于內排序。
內排序有可以分為以下幾類：
1、插入排序：直接插入排序、二分法插入排序、希爾排序。
2、選擇排序：直接選擇排序、堆排序。
3、交換排序：冒泡排序、快速排序。
4、歸并排序
5、基數(shù)排序
冒泡排序
1.基本思想：兩個數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來。
2.過程：
比較相鄰的兩個數(shù)據(jù)，如果第二個數(shù)小，就交換位置。
從后向前兩兩比較，一直到比較最前兩個數(shù)據(jù)。最終最小數(shù)被交換到起始的位置，這樣第一個最小數(shù)的位置就排好了。
繼續(xù)重復上述過程，依次將第2.3...n-1個最小數(shù)排好位置。
3.平均時間復雜度：O(n2)
4.優(yōu)化：
針對問題：
數(shù)據(jù)的順序排好之后，冒泡算法仍然會繼續(xù)進行下一輪的比較，直到arr.length-1次，后面的比較沒有意義的。
方案：
設置標志位flag，如果發(fā)生了交換flag設置為true；如果沒有交換就設置為false。
這樣當一輪比較結束后如果flag仍為false，即：這一輪沒有發(fā)生交換，說明數(shù)據(jù)的順序已經排好，沒有必要繼續(xù)進行下去。
5.Python代碼實現(xiàn)：
@staticmethoddef bubble_sort(arr):
? ? for i in range(len(arr)):
? ? ? ? not_change = True
? ? ? ? for j in range(len(arr) - 1, i - 1, -1):? ? ? ? ?
if arr[j] < arr[j - 1]:
? ? ? ? ? ? ? ? tmp = arr[j]
? ? ? ? ? ? ? ? arr[j] = arr[j - 1]
? ? ? ? ? ? ? ? arr[j - 1] = tmp
? ? ? ? ? ? ? ? not_change = False
? ? ? ? if not_change:? ? ? ? ? ?
break
return arr
選擇排序
1.基本思想：
在長度為N的無序數(shù)組中，第一次遍歷n-1個數(shù)，找到最小的數(shù)值與第一個元素交換；
第二次遍歷n-2個數(shù)，找到最小的數(shù)值與第二個元素交換；
第n-1次遍歷，找到最小的數(shù)值與第n-1個元素交換，排序完成。
2.過程
3.平均時間復雜度：O(n2)
4.python代碼實現(xiàn)：
@staticmethoddef select_sort(arr):
? ? for index in range(len(arr)):
? ? ? ? min_index = index? ? ? ?
for j in range(index + 1, len(arr)):? ? ? ? ? ?
if arr[j] < arr[min_index]:
? ? ? ? ? ? ? ? min_index = j? ? ? ?
if min_index != index:
? ? ? ? ? ? tmp = arr[index]
? ? ? ? ? ? arr[index] = arr[min_index]
? ? ? ? ? ? arr[min_index] = tmp? ?
return arr
插入排序
1.基本思想：
在要排序的一組數(shù)中，假定前n-1個數(shù)已經排好序，現(xiàn)在將第n個數(shù)插到前面的有序數(shù)列中，使得這n個數(shù)也是排好順序的。如此反復循環(huán)，直到全部排好順序。
2.過程：
3.平均時間復雜度：O(n2)
4.python代碼實現(xiàn)：
@staticmethoddef insert_sort(arr):
? ? for index in range(len(arr) - 1):? ? ? ?
for j in range(index + 1, 0, -1):? ? ? ? ?
if arr[j] < arr[j - 1]:
? ? ? ? ? ? ? tmp = arr[j]
? ? ? ? ? ? ? ? arr[j] = arr[j - 1]
? ? ? ? ? ? ? ? arr[j - 1] = tmp? ? ? ? ? ?
else:? ? ? ? ? ? ? ?
break
? ? return arr
希爾排序
1.基本思想：
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
2.過程：3.平均時間復雜度：O（n*logn）
4.python代碼實現(xiàn)：
def shell_sort(arr):
? ? gap = len(arr)? ?
while True:
? ? ? ? gap = int(gap / 2)? ? ? ?
for arr_index in range(gap):
? ? ? ? ? ? print('arr_index:', arr_index)? ? ? ? ? ?
for element in range(arr_index, len(arr) - 1, gap):
? ? ? ? ? ? ? ? print('element:', element)? ? ? ? ? ? ? ?
for j in range(element, arr_index, -gap):? ? ? ? ? ? ? ? ? ?
# print('j', j)
? ? ? ? ? ? ? ? ? ? if arr[j] < arr[element - gap]:
? ? ? ? ? ? ? ? ? ? ? ? tmp = arr[element - gap]
? ? ? ? ? ? ? ? ? ? ? ? arr[element - gap] = arr[j]
? ? ? ? ? ? ? ? ? ? ? ? arr[j] = tmp? ? ? ? ? ? ? ? ? ?
else:? ? ? ? ? ? ? ? ? ? ? ?
break
? ? ? ? if gap == 1:? ? ? ? ? ?
break
? ? return arr
快速排序
1.基本思想：（分治）
先從數(shù)列中取出一個數(shù)作為key值；
將比這個數(shù)小的數(shù)全部放在它的左邊，大于或等于它的數(shù)全部放在它的右邊；
對左右兩個小數(shù)列重復第二步，直至各區(qū)間只有1個數(shù)。
2.過程
1）初始時 i = 0; j = 9; key=72
由于已經將a[0]中的數(shù)保存到key中，可以理解成在數(shù)組a[0]上挖了個坑，可以將其它數(shù)據(jù)填充到這來。
從j開始向前找一個比key小的數(shù)。當j=8，符合條件，a[0] = a[8] ; i++ ; 將a[8]挖出再填到上一個坑a[0]中。
這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個坑。
這次從i開始向后找一個大于key的數(shù)，當i=3，符合條件，a[8] = a[3] ; j-- ; 將a[3]挖出再填到上一個坑中。
image
2）此時 i = 3; j = 7; key=72
再重復上面的步驟，先從后向前找，再從前向后找。
從j開始向前找，當j=5，符合條件，將a[5]挖出填到上一個坑中，a[3] = a[5]; i++;
從i開始向后找，當i=5時，由于i==j退出。
此時，i = j = 5，而a[5]剛好又是上次挖的坑，因此將key填入a[5]。
image
3）可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對a[0…4]和a[6…9]這二個子區(qū)間重復上述步驟就可以了。
image
3.平均時間復雜度：O(N*logN)
4.Python代碼實現(xiàn)：
def quick_sort(self, arr, left, right):
? ? if left >= right:? ? ? ? return
? ? key = arr[left]
? ? i = left
? ? j = right? ? while i < j:? ? ? ?
while i < j and arr[j] >= key:
? ? ? ? ? ? j -= 1
? ? ? ? if i < j:
? ? ? ? ? ? arr[i] = arr[j]
? ? ? ? ? ? i += 1
? ? ? ? while i < j and arr[i] < key:
? ? ? ? ? ? i += 1
? ? ? ? if i < j:
? ? ? ? ? ? arr[j] = arr[i]
? ? ? ? ? ? j -= 1
? ? arr[i] = key
? ? self.quick_sort(arr, left, i - 1)
? ? self.quick_sort(arr, i + 1, right)? ?
return arr
堆排序
堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡單了解下堆結構。
堆
堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。如下圖：
image
同時，我們對堆中的結點按層進行編號，將這種邏輯結構映射到數(shù)組中就是下面這個樣子
image
該數(shù)組從邏輯上講就是一個堆結構，我們用簡單的公式來描述一下堆的定義就是：
大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序基本思想及步驟
堆排序的基本思想是：將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執(zhí)行，便能得到一個有序序列了。
步驟一 構造初始堆。將給定無序序列構造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)。
image
假設給定無序序列結構如下
1、此時我們從最后一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點 arr.length/2-1=5/2-1=1，也就是下面的6結點），從左至右，從下至上進行調整。
image
2、找到第二個非葉節(jié)點4，由于[4,9,8]中9元素最大，4和9交換。
image
這時，交換導致了子根[4,5,6]結構混亂，繼續(xù)調整，[4,5,6]中6最大，交換4和6。
image
步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然后繼續(xù)調整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復進行交換、重建、交換。
3、將堆頂元素9和末尾元素4進行交換
image
4、重新調整結構，使其繼續(xù)滿足堆定義
image
5、再將堆頂元素8與末尾元素5進行交換，得到第二大元素8.
image
后續(xù)過程，繼續(xù)進行調整，交換，如此反復進行，最終使得整個序列有序
501521032602_.pi
再簡單總結下堆排序的基本思路：
a.將無需序列構建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端;
c.重新調整結構，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調整+交換步驟，直到整個序列有序。
