一蜡塌、排序算法分類
十大排序算法可以分為兩大類：
非線性時間排序：通過比較元素來決定元素間的相對次序，其時間復雜度不能突破O(nlogn)
線性時間排序：不通過比較元素來決定元素間的相對次序棋凳，可以突破比較排序時間下界弧关，以線性時間運行
其中：穩(wěn)定是指如果a原本在b前面两蟀，而a=b，排序之后a仍然在b的前面履澳，不穩(wěn)定是a可能會出現(xiàn)在b的后面。
二怀跛、非線性時間排序算法
1. 冒泡排序（Bubble Sort）
· 遍歷一遍距贷，比較相鄰元素大小，若元素順序錯誤則交換位置吻谋，一遍結(jié)束后忠蝗，一個元素的位置排好；
· 重復遍歷列表中未排序元素漓拾，直至完成列表排序阁最；(如果在一次遍歷中戒祠，沒有發(fā)生元素交換行為，則說明列表所有元素順序正確速种，排序完成)
每輪只對相鄰兩個數(shù)比較與交換姜盈，每輪會將一個最值交換到數(shù)據(jù)列首或尾，像冒泡一樣哟旗，n個數(shù)據(jù)會操作n-1輪贩据。時間復雜度O(n^2)，額外空間開銷在交換數(shù)據(jù)時那一個過渡空間闸餐，空間復雜度O(1)饱亮。
代碼實現(xiàn)：
def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
n = len(arr)
swapped = True
x = -1
while swapped:
swapped = False
x = x + 1
for i in range(1, n - x):
if arr[i-1] > arr[i]:
swap(i-1, i)
swapped = True
return arr
2. 簡單選擇排序（Select Sort）
· 將輸入列表/數(shù)組分為兩部分：已經(jīng)排序的子列表和剩余要排序的子列表；
· 在未排序的子列表中找到最小的元素舍沙，并將其按順序放置在排序的子列表中近上，重復此過程，直至列表完全排序拂铡；
n個數(shù)操作n-1輪壹无，每輪選一個最值，時間復雜度O(n^2)感帅，額外空間開銷在交換數(shù)據(jù)時那一個過渡空間斗锭，空間復雜度O(1)。
代碼實現(xiàn)：
def select_sort(arr):
for i in range(len(arr)):
minvalue_idx = i
for j in range(i, len(arr)):
if arr[j] < arr[minvalue_idx]:
minvalue_idx = j
arr[i], arr[minvalue_idx] = arr[minvalue_idx], arr[i]
return arr
3. 快速排序（Quick Sort)
· 從數(shù)組中挑出一個元素失球，稱為“基準”（pivot）;
· 分區(qū)：將所有比基準值小的元素擺放在基準值前岖是，比基準值大的元素擺在基準后值，基準值位于數(shù)列的中間位置实苞；
· 遞歸地把小于基準值的子數(shù)列和大于基準值的子數(shù)列排序普碎；
遞歸到最底部的判斷條件是數(shù)列的大小是0或者1想鹰，此時該數(shù)列顯然已經(jīng)有序窖剑。
選取基準值數(shù)種具體方法煤惩，其選取方法對排序的時間性能有關。常見會選取數(shù)組第一個數(shù)作為基準猾浦。
1）設置兩個變量i陆错、j，排序開始的時候：i=0, j=N-1金赦；
2）以第一個數(shù)組元素作為基準危号，賦值給pivot，即key=A[0]素邪；
3）從j開始向前搜索外莲，即由后向前搜索(j--)，找到第一個小于pivot的A[j]，將A[j]和A[i]互換偷线；
4）從i開始向后搜索磨确，即由前向后搜索(i++)，找到第一個大于pivot的A[i]声邦，將A[i]和A[j]互換乏奥；
5）重復3、4步亥曹，直到i=j;（3,4步中邓了，沒找到符合條件的值，即3中的A[j]不小于pivot媳瞪，4中的A[i]不大于pivot時骗炉，改變i, j的值，j = j-1蛇受，i = i+1）
快排是原地排序句葵，不需要輔助數(shù)組，但是遞歸調(diào)用需要輔助棧兢仰≌д桑快速排序最好的情況下是每次都正好將數(shù)組對半分，這樣遞歸調(diào)用次數(shù)才是最少的把将，這種情況下比較次數(shù)為 Cn=2Cn/2+n轻专，復雜度為 O(nlogn)。最壞的情況下察蹲，第一次從最小的元素切分铭若，第二次從第二小的元素切分，如此這般递览。因此最壞的情況下需要比較n^2/2，為了防止數(shù)組從最開始就是有序的瞳腌，在進行快排時需要隨機打亂數(shù)組绞铃。
時間復雜度：快排涉及到遞歸調(diào)用，因此其時間復雜度與遞歸算法的復雜度相關嫂侍，T[n] = aT[n/b] + f(n) 儿捧。
最優(yōu)快排：每一次取到的元素都剛好平分整個數(shù)組，T[n] = 2T[n/2] + f(n)挑宠， T[n/2]為平分后的子數(shù)組的時間復雜度菲盾，f[n] 為平分這個數(shù)組時所花的時間。遞歸推算下來時間復雜度O( nlogn )各淀。最差的情況就是每次取到的元素是數(shù)組中最大/或者最小的懒鉴，此時時間復雜度O(n^2)。平均時間復雜度O(nlogn)。
空間復雜度：就地快速排序使用的空間O(1)临谱，是常數(shù)級璃俗，而真正消耗空間的就是遞歸調(diào)用，因為每次遞歸就要保持一些數(shù)據(jù)悉默。額外空間開銷出在暫存基準值,最優(yōu)情況下空間復雜度為O(logn)城豁，每次都平分數(shù)組，最差情況下空間復雜度為O(n)抄课，每次取到的元素是最值唱星。
代碼實現(xiàn)：
def partition(arr, low, high):
pivot = arr[low]
while low < high:
while low < high and arr[high] >= pivot:
high = high -1
arr[low] = arr[high]
while low < high and arr[low] <= pivot:
low = low + 1
arr[high] = arr[low]
arr[low] = pivot
return low
def QucikSort(arr, low, high):
if low >= high:
return
pivot_idx = partition(arr, low, high)
QucikSort(arr, low, pivot_idx-1)
QucikSort(arr, pivot_idx+1, high)
return arr
4. 簡單插入排序（Insert Sort）
· 從第一個元素開始，該元素可被認為已經(jīng)被排序跟磨；
· 取出下一個元素间聊，在已經(jīng)排序的元素列表中從后向前掃描；
· 如果該已排序元素大于新元素吱晒，將新元素向前移動至下一位置甸饱；
· 重復上一步驟，直到找到已排序的元素小于或等于新元素的位置仑濒；
· 將新元素插入到該位置后叹话；
簡單插入排序需要操作n-1輪，每輪將一個未排序元素插入排好序列墩瞳，開始時默認第一個元素有序驼壶，將剩余n-1個數(shù)逐個插入。插入操作具體包括：比較確定插入位置喉酌，數(shù)據(jù)移位騰出合適空位热凹。
每輪操作O(n)次，共O(n)輪泪电，時間復雜度O(n^2)般妙；
額外空間開銷是數(shù)據(jù)移位時產(chǎn)生的一個過渡空間，空間復雜度為O(1)相速。
def InsertSort(arr):
n = len(arr)
if n<=1: return arr
for i in range(1,n):
j = i
target = arr[i]
while j>0 and target<arr[j-1]:
arr[j]=arr[j-1]
j=j-1
arr[j] = target
return arr
5. 堆排序（Heap Sort）
堆排序是利用堆這種數(shù)據(jù)結(jié)構而設計的一種排序算法碟渺，堆排序是一種選擇排序。堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值突诬，稱為大頂堆苫拍；每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆旺隙。
對堆中的結(jié)點按層進行編號绒极，將這種邏輯結(jié)構映射到數(shù)組中如下:
該數(shù)組從邏輯上講就是一個堆結(jié)構，用公式來描述堆的定義就是：
大頂堆：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í)行高蜂，便能得到一個有序序列聪黎。
步驟一、構造初始堆：將給定無序序列構造成一個大頂堆（一般升序采用大頂堆备恤，降序采用小頂堆）
- 假設給定無序序列結(jié)構如下：
- 此時從最后一個非葉子結(jié)點開始（葉結(jié)點自然不用調(diào)整稿饰，第一個非葉子節(jié)點len(arr)/2-1 = 5/2-1=1，也就是下面的6結(jié)點）露泊，從左至右喉镰，從下至上進行調(diào)整。
- 找到第二個非葉子節(jié)點4惭笑，其中4,9,8中9最大侣姆，4和9交換。
此時沉噩，交換導致了子根4,5,6結(jié)構混亂捺宗，繼續(xù)調(diào)整，4,5,6中6最大川蒙，4和6交換位置蚜厉，將無序序列構造成了一個大頂堆。
步驟二畜眨、將堆頂元素與末尾元素進行交換昼牛，使末尾元素最大，然后繼續(xù)調(diào)整堆康聂，再將堆頂元素與末尾元素交換贰健，得到第二大元素，如此反復進行交換恬汁、重建伶椿、交換，直到整個序列有序蕊连。
- 將堆頂元素9與末尾元素4進行交換
- 重新調(diào)整結(jié)構，使其繼續(xù)滿足堆定義
- 再將堆頂元素8與末尾元素5進行交換游昼，得到第二大元素8
后續(xù)過程甘苍，繼續(xù)進行調(diào)整、交換烘豌，如此反復進行载庭，最終使得整個序列有序。
總結(jié)：
· 將無序序列構建成一個堆，根據(jù)升序囚聚、降序需求選擇大頂堆或小頂堆靖榕；
· 將堆頂元素與末尾元素交換，將最大元素“沉”到數(shù)組末端顽铸；
· 重新調(diào)整結(jié)構茁计，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素谓松，反復執(zhí)行調(diào)整+交換步驟星压，直到整個序列有序；
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i +2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] #exchange
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build a maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)
# exchange the max to the end
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
6. 希爾排序（Shell Sort）
7. 歸并排序（Merge Sort）
歸并排序是建立在歸并操作上的一種有效的排序方法鬼譬，該算法是分治法（Divide and Conquer）的一個非常典型的應用娜膘。先使每個子序列有序，再將兩個有序子序列合并成一個有序序列稱為2-路歸并优质。
· 把長度為n的輸入序列分成為兩個長度為n/2的子序列竣贪；
· 對這兩個子序列分別采用歸并排序；
· 將兩個排好序的子序列合并成一個最終的排序序列巩螃；
歸并排序包括了Sort和Merge兩部分演怎。當有n個待排序元素時，需要進行l(wèi)ogn輪歸并排序牺六，每一輪歸并颤枪，其比較元素不超過n個，因此歸并排序時間復雜度為nlogn淑际；而在排序時需記錄的中間元素個數(shù)與待排序元素個數(shù)相等畏纲，因此空間復雜度為O(n)。
def merge_sort(arr, low, high):
if low >= high: return
mid = (low + high) // 2
merge_sort(arr, low, mid)
merge_sort(arr, mid+1, high)
merge(arr, low, mid, high)
def merge(arr, low, mid, high):
container = []
i, j = low, mid + 1
while i<=mid and j<=high:
if arr[i] <= arr[j]:
container.append(arr[i])
i = i + 1
else:
container.append(arr[j])
j = j + 1
if i<=mid:
container.extend(arr[i:mid+1])
elif j<=high:
container.extend(arr[j:high+1])
arr[low:high+1] = container
