## 1.冒泡排序
```python
# 2 冒泡排序：它重復(fù)的走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來，走訪數(shù)列的工作是重復(fù)的執(zhí)行到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)完成排序。
#時(shí)間復(fù)雜度 O(n^2)
#空間復(fù)雜度：O(1)
#穩(wěn)定性：穩(wěn)定
def bubble_sort(blist):
? ? count = len(blist)
? ? for i in range(0,count):
? ? ? ? for j in range(i+1,count):
? ? ? ? ? ? if blist[i] > blist[j]:
? ? ? ? ? ? ? ? blist[i],blist[j] = blist[j],blist[i]
? ? return blist
print(bubble_sort([4,5,6,7,8,2,3,1,0]))
```
___
## 2.插入排序
```python
#1 插入排序:插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的，個(gè)數(shù)加1 的有序數(shù)據(jù)，算法用于少量數(shù)據(jù)的排序，首先將第一個(gè)作為已經(jīng)排好序的，然后每次從后的取出插入到前面并排序。
#時(shí)間復(fù)雜度 O(n^2)
#空間復(fù)雜度：O(1)
#穩(wěn)定性：穩(wěn)定
def insert_sort(ilist):
? ? for i in range(len(ilist)):
? ? ? ? for j in range(i):
? ? ? ? ? ? if ilist[i] < ilist[j]:
? ? ? ? ? ? ? ? ilist.insert(j,ilist.pop(i))
? ? ? ? ? ? ? ? break
? ? return ilist
print(insert_sort([4,6,7,3,2,1,8,0]))
```
___
## 3.選擇排序
```python
#3 選擇排序 ： 第一趟，在待排序記錄r1 。。。r(n)中選出最小的記錄，將它與r1 交換，第二趟，在待排序記錄r2 ~ r(n) 中選出最小的記錄，將它與 r2 交換，以此類推，第i趟在待排序記錄 r[i]~r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長(zhǎng)直到全部排序完畢。
#時(shí)間復(fù)雜度 O(n^2)
#空間復(fù)雜度：O(1)
#穩(wěn)定性：不穩(wěn)定
def select_sort(slist):
? ? #外層循環(huán)控制循環(huán)次數(shù)
? ? for i in range(len(slist)):
? ? ? ? #假設(shè)找到的最小元素下標(biāo)為j
? ? ? ? x = i
? ? ? ? #尋找最小元素的過程
? ? ? ? for j in range(i,len(slist)):
? ? ? ? ? ? #假設(shè)最小下標(biāo)的值，大于循環(huán)中一個(gè)元素，那么就改變最小值的下標(biāo)
? ? ? ? ? ? if slist[j] < slist[x]:
? ? ? ? ? ? ? ? x = j
? ? ? ? #循環(huán)一開始就假設(shè)把最小值的下標(biāo)賦值給變量 x
? ? ? ? # 在不停的循環(huán)中，不停的交換兩個(gè)不一樣大小的值
? ? ? ? slist[i],slist[x] = slist[x],slist[i]
? ? #返回 排好序的列表
? ? return slist
if __name__ == '__main__':
? ? arrayList = [4,5,6,7,3,2,6,9,8]
? ? select_sort(arrayList)
? ? print(arrayList)
```
___
## 4.希爾排序
```python
#4 希爾排序 ： 希爾排序 是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰好被分成一組，算法終止
#時(shí)間復(fù)雜度 O(n^2)
#空間復(fù)雜度：O(nlogn)
#穩(wěn)定性：不穩(wěn)定
def shell_sort(slist):
? ? count = len(slist)
? ? step = 2
? ? group = count // step
? ? while group>0:
? ? ? ? for i in range(group):
? ? ? ? ? ? j = i + group
? ? ? ? ? ? while j < count:
? ? ? ? ? ? ? ? key = slist[j]
? ? ? ? ? ? ? ? k = j - group
? ? ? ? ? ? ? ? while k >= 0:
? ? ? ? ? ? ? ? ? ? if slist[k] > key:
? ? ? ? ? ? ? ? ? ? ? ? slist[k+group] = slist[k]
? ? ? ? ? ? ? ? ? ? ? ? slist[k] = key
? ? ? ? ? ? ? ? ? ? k = k - group
? ? ? ? ? ? ? ? j = j + group
? ? ? ? group = group // step
? ? return slist
# print(shell_sort([4,5,7,3,2,6,9,8,0]))
def ShellSort(arrList):
? ? arrayLen = len(arrList)
? ? h = 1
? ? while h < arrayLen//3:
? ? ? ? h = h * 3 + 1
? ? ? ? #插入排序的方法，判斷是不是后一個(gè)比前一個(gè)要小
? ? ? ? #如果是則交換
? ? while h >= 1:
? ? ? ? for i in range(h,arrayLen):
? ? ? ? ? ? j = i
? ? ? ? ? ? while j >= h and arrList[j] < arrList[j-h]:
? ? ? ? ? ? ? ? arrList[j] ,arrList[j-h] = arrList[j-h],arrList[j]
? ? ? ? ? ? ? ? j -= h
? ? ? ? h? //= 3
if __name__ == '__main__':
? ? arrList = [14,33,27,10,35,19,42,44]
? ? ShellSort(arrList)
? ? print(arrList)
```
___
## 5.歸并排序
```python
#? ? ? 當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
"""
歸并排序：采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并
時(shí)間復(fù)雜度：O(nlog?n)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定
"""
# 歸并排序 Merge_Sort
def MergeSort(arrayList):
? ? arrayLen = len(arrayList)
? ? #判斷輸入?yún)?shù)的正確性,如果長(zhǎng)度小于1，就說明為1
? ? if arrayLen <= 1:
? ? ? ? return arrayList
? ? midIndex = arrayLen//2
? ? #左邊的部分去做 MergeSort
? ? leftArray = MergeSort(arrayList[:midIndex])
? ? #右邊的去做 MergeSort
? ? rightArray = MergeSort(arrayList[midIndex:])
? ? #將左右兩邊合并，稱為一個(gè)新的數(shù)組，并已經(jīng)排序成功
? ? retArray = MergeCore(leftArray,rightArray)
? ? return retArray
def MergeCore(leftArray,rightArray):
? ? #首先需要定義兩個(gè)指針,這兩個(gè)指針，分別指向這兩個(gè)數(shù)組的第一個(gè)元素
? ? leftIndex = 0
? ? rightIndex = 0
? ? #獲取兩個(gè)數(shù)組的長(zhǎng)度，用于指出上面兩個(gè)指針的邊界是什么
? ? leftLen = len(leftArray)
? ? rightLen = len(rightArray)
? ? #定義一個(gè)返回的列表,這一步就代表空間復(fù)雜度至少是 O(n)
? ? retList = []
? ? #循環(huán)兩個(gè)數(shù)組尋找最小值加入到返回值的數(shù)組中
? ? while leftIndex < leftLen and rightIndex < rightLen:
? ? ? ? if leftArray[leftIndex] < rightArray[rightIndex]:
? ? ? ? ? ? retList.append(leftArray[leftIndex])
? ? ? ? ? ? leftIndex += 1
? ? ? ? else:
? ? ? ? ? ? retList.append(rightArray[rightIndex])
? ? ? ? ? ? rightIndex += 1
? ? #下面的代碼是將剩余的數(shù)組中內(nèi)容放置在返回的數(shù)組中
? ? retList.extend(leftArray[leftIndex:])
? ? # while leftIndex < leftLen:
? ? #? ? retList.append(leftArray[leftIndex])
? ? #? ? leftIndex += 1
? ? retList.extend(rightArray[rightIndex:])
? ? # while rightIndex < rightLen:
? ? #? ? retList.append(rightArray[rightIndex])
? ? #? ? rightIndex += 1
? ? return retList
if __name__ == '__main__':
? ? # 14,33,27,10,35,19,42,44
? ? retList = MergeSort([14,33,27,10,35,19,42,44])
? ? print(retList)
```
___
## 6.快速排序
```python
"""
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
時(shí)間復(fù)雜度：O(nlog?n)
空間復(fù)雜度：O(nlog?n)
穩(wěn)定性：不穩(wěn)定
"""
#快排的主函數(shù)，傳入?yún)?shù)為一個(gè)列表，左右兩端的下標(biāo)
def QuickSort(array,leftIndex=0,rightIndex=None):
? ? #數(shù)組的長(zhǎng)度
? ? arrayLen = len(array)
? ? #長(zhǎng)度為1 的話 或者 空 的話 直接返回 數(shù)組
? ? if arrayLen <= 1:
? ? ? ? return array
? ? #程序一開始 如果沒有給一個(gè)最右邊的索引值導(dǎo)入話，那么我們就給它 賦值一個(gè) 就是數(shù)組的最右邊的 那個(gè)索引值。
? ? if rightIndex == None:
? ? ? ? rightIndex = arrayLen - 1
? ? # 保護(hù)條件，只有滿足? 左邊索引小于右邊索引的時(shí)候 再開始排序
? ? if leftIndex < rightIndex:
? ? ? ? #找到 基準(zhǔn)的 索引值 傳入?yún)?shù)，通過Partitions函數(shù)，獲取k下標(biāo)值
? ? ? ? pivot = partition(array,leftIndex,rightIndex)
? ? ? ? #遞歸前后半?yún)^(qū) 對(duì)基準(zhǔn)前面不部分繼續(xù)快排
? ? ? ? QuickSort(array,leftIndex,pivot - 1)
? ? ? ? #對(duì)基準(zhǔn)后半積分繼續(xù)快排
? ? ? ? QuickSort(array,pivot + 1,rightIndex)
def partition(array,leftIndex,rightIndex):
? ? pivotValue = array[rightIndex]
? ? #將最左側(cè)的 索引值 給 i
? ? i? = leftIndex
? ? #將最右側(cè)的 索引的前一個(gè) 給j
? ? j = rightIndex -1
? ? #當(dāng)left下標(biāo)，小于right下標(biāo)的情況下，此時(shí)判斷二者移動(dòng)是否相交，若未相交，則一直循環(huán)
? ? while i < j:
? ? ? ? # 當(dāng)left對(duì)應(yīng)的值大于錨點(diǎn) 基準(zhǔn)點(diǎn) 參考值，就一直向左移動(dòng)
? ? ? ? while j > leftIndex and array[j] > pivotValue:
? ? ? ? ? ? j -= 1
? ? ? ? #當(dāng)left對(duì)應(yīng)的值小于基準(zhǔn)點(diǎn)參考值，就一直向右移動(dòng)
? ? ? ? while i < rightIndex and array[i] <= pivotValue:
? ? ? ? ? ? i += 1
? ? ? ? #若移動(dòng)完，二者仍未相遇則交換下標(biāo)對(duì)應(yīng)的值
? ? ? ? if i < j:
? ? ? ? ? ? array[j],array[i] = array[i],array[j]
? ? ? ? ? ? i+=1
? ? ? ? ? ? j-=1
? ? #若移動(dòng)完，已經(jīng)相遇，則交換right對(duì)應(yīng)的值和參考值
? ? array[i],array[rightIndex] = array[rightIndex],array[i]
? ? # 返回 一個(gè) 索引值
? ? return i
# 《算法導(dǎo)論》中的快排程序
def partition2(array,leftIndex,rightIndex):
? ? #設(shè)置一個(gè) 左邊的指針位置 為 左側(cè)的 前一個(gè)
? ? i = leftIndex -1
? ? #遍歷 除 基準(zhǔn)數(shù)之外的 數(shù)
? ? for j in range(leftIndex,rightIndex):
? ? ? ? #比較 遍歷的數(shù) 和 基準(zhǔn)數(shù) ，若是小于基準(zhǔn)數(shù) 則 換到數(shù)組前面去
? ? ? ? if array[j] < array[rightIndex]:
? ? ? ? ? ? #交換位置，將遍歷的比 基準(zhǔn)數(shù)小的數(shù) 放到 我們指針 的 后一個(gè)上，然后 這個(gè)時(shí)候指針向后移一位。當(dāng)遍歷的數(shù)大于我們的基準(zhǔn)數(shù)的時(shí)候，不移動(dòng)，而且 指針也不發(fā)生變化，那么 當(dāng)我們遍歷完一圈以后，把 我們的基準(zhǔn)數(shù) 放到 索引i 的后一個(gè) 位置，那么就形成了 一個(gè) 基準(zhǔn)數(shù) 左邊都是比它小的數(shù)，基準(zhǔn)數(shù)右邊 都是比它大的數(shù) 這樣的模式。然后要把 索引 i 的后一個(gè)位置 作為基準(zhǔn)數(shù) 與 原基準(zhǔn)數(shù) 交換位置，進(jìn)而可以第二次來 遍歷比較。
? ? ? ? ? ? array[j],array[i+1] = array[i+1],array[j]
? ? ? ? ? ? i += 1
? ? #遍歷完了以后，將 left 位置上的數(shù) 和 最后一個(gè) 數(shù)? 即 right 上的數(shù)互換位置，就 重置 基準(zhǔn)數(shù)了。
? ? array[rightIndex],array[i+1] = array[i+1],array[rightIndex]
? ? #返回基準(zhǔn)的下標(biāo)
? ? return i+1
if __name__ == '__main__':
? ? array = [14,33,27,10,35,19,42,44]
? ? QuickSort(array)
? ? print(array)
```
排序內(nèi)存使用
排序執(zhí)行時(shí)間：
排序復(fù)雜度比較：
