上期為大家講解了排序算法常見的幾個概念：
相關(guān)性：排序時是否需要比較元素
穩(wěn)定性：相同元素排序后是否可能打亂
時間空間復(fù)雜度：隨著元素增加時間和空間隨之變化的函數(shù)
如果有遺忘的同學(xué)可以看排序算法——（1）簡介這篇文章復(fù)習(xí)一下奈辰。
今天將為大家介紹常用的十大排序算法中最簡單的五種（冒泡回溺、選擇念秧、插入、希爾幸冻、歸并），主要從：過程圖解摹察、算法思想奶躯、代碼實現(xiàn)、算法分析這四個方面講解特漩，建議大家看完之后自己動手練習(xí)加強(qiáng)記憶吧雹！
注：本文使用的復(fù)雜度均為最壞復(fù)雜度
冒泡排序（Bubble Sort）涂身，是一種計算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法雄卷。它重復(fù)地走訪過要排序的元素列，依次比較兩個相鄰的元素蛤售，一層一層的將較大的元素往后移動丁鹉，其現(xiàn)象和氣泡在上升過程中慢慢變大類似，故成為冒泡排序悴能。
從第一個和第二個開始比較揣钦，如果第一個比第二個大，則交換位置漠酿，然后比較第二個和第三個冯凹，逐漸往后
經(jīng)過第一輪后最大的元素已經(jīng)排在最后，所以重復(fù)上述操作的話第二大的則會排在倒數(shù)第二的位置记靡。
那重復(fù)上述操作n-1次即可完成排序谈竿，因為最后一次只有一個元素所以不需要比較
def bubble_sort(arr):
"""冒泡排序"""
# 第一層for表示循環(huán)的遍數(shù)
for i in range(len(arr) - 1):
# 第二層for表示具體比較哪兩個元素
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
# 如果前面的大于后面的团驱，則交換這兩個元素的位置
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
冒泡排序是一種簡單直接暴力的排序算法摸吠，為什么說它暴力？因為每一輪比較可能多個元素移動位置嚎花，而元素位置的互換是需要消耗資源的寸痢，所以這是一種偏慢的排序算法，僅適用于對于含有較少元素的數(shù)列進(jìn)行排序紊选。
穩(wěn)定性：我們從代碼中可以看出只有前一個元素大于后一個元素才可能交換位置啼止，所以相同元素的相對順序不可能改變，所以它是穩(wěn)定排序
比較性：因為排序時元素之間需要比較兵罢，所以是比較排序
時間復(fù)雜度：因為它需要雙層循環(huán)n*(n-1))献烦，所以平均時間復(fù)雜度為O(n^2)
空間復(fù)雜度：只需要常數(shù)個輔助單元，所以空間復(fù)雜度為O(1)卖词，我們把空間復(fù)雜度為O(1)的排序成為原地排序（in-place）
記憶方法：想象成氣泡巩那，一層一層的往上變大
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最屑春帷（或最大）的一個元素噪生，存放在序列的起始位置，所以稱為：選擇排序
設(shè)第一個元素為比較元素东囚，依次和后面的元素比較跺嗽，比較完所有元素找到最小的元素，將它和第一個元素互換
重復(fù)上述操作页藻，我們找出第二小的元素和第二個位置的元素互換桨嫁，以此類推找出剩余最小元素將它換到前面，即完成排序
def selection_sort(arr):
"""選擇排序"""
# 第一層for表示循環(huán)選擇的遍數(shù)
for i in range(len(arr) - 1):
# 將起始元素設(shè)為最小元素
min_index = i
# 第二層for表示最小元素和后面的元素逐個比較
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果當(dāng)前元素比最小元素小份帐，則把當(dāng)前元素角標(biāo)記為最小元素角標(biāo)
min_index = j
# 查找一遍后將最小元素與起始元素互換
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr
選擇排序和冒泡排序很類似瞧甩，但是選擇排序每輪比較只會有一次交換，而冒泡排序會有多次交換弥鹦，交換次數(shù)比冒泡排序少肚逸，就減少cpu的消耗，所以在數(shù)據(jù)量小的時候可以用選擇排序彬坏，實際適用的場合非常少朦促。
比較性：因為排序時元素之間需要比較，所以是比較排序
穩(wěn)定性：因為存在任意位置的兩個元素交換栓始，比如[5, 8, 5, 2]务冕，第一個5會和2交換位置，所以改變了兩個5原來的相對順序幻赚，所以為不穩(wěn)定排序禀忆。
時間復(fù)雜度：我們看到選擇排序同樣是雙層循環(huán)n*(n-1))，所以時間復(fù)雜度也為：O(n^2)
空間復(fù)雜度：只需要常數(shù)個輔助單元落恼，所以空間復(fù)雜度也為O(1)
記憶方法：選擇對象要先選最小的箩退，因為嫩，哈哈
插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法戴涝。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)钻蔑，在已排序序列中從后向前掃描啥刻，找到相應(yīng)位置并插入。
從第二個元素開始和前面的元素進(jìn)行比較咪笑，如果前面的元素比當(dāng)前元素大可帽，則將前面元素 后移，當(dāng)前元素依次往前窗怒，直到找到比它小或等于它的元素插入在其后面
然后選擇第三個元素映跟，重復(fù)上述操作钝满，進(jìn)行插入
依次選擇到最后一個元素，插入后即完成所有排序
def insertion_sort(arr):
"""插入排序"""
# 第一層for表示循環(huán)插入的遍數(shù)
for i in range(1, len(arr)):
# 設(shè)置當(dāng)前需要插入的元素
current = arr[i]
# 與當(dāng)前元素比較的比較元素
pre_index = i - 1
while pre_index >= 0 and arr[pre_index] > current:
# 當(dāng)比較元素大于當(dāng)前元素則把比較元素后移
arr[pre_index + 1] = arr[pre_index]
# 往前選擇下一個比較元素
pre_index -= 1
# 當(dāng)比較元素小于當(dāng)前元素申窘，則將當(dāng)前元素插入在 其后面
arr[pre_index + 1] = current
return arr
插入排序的適用場景：一個新元素需要插入到一組已經(jīng)是有序的數(shù)組中弯蚜，或者是一組基本有序的數(shù)組排序。
比較性：排序時元素之間需要比較剃法，所以為比較排序
穩(wěn)定性：從代碼我們可以看出只有比較元素大于當(dāng)前元素碎捺，比較元素才會往后移動，所以相同元素是不會改變相對順序
時間復(fù)雜度：插入排序同樣需要兩次循壞一個一個比較贷洲，故時間復(fù)雜度也為O(n^2)
空間復(fù)雜度：只需要常數(shù)個輔助單元收厨，所以空間復(fù)雜度也為O(1)
記憶方法：想象成在書架中插書：先找到相應(yīng)位置，將后面的書往后推优构，再將書插入
希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量(間隔)排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本钦椭，它與插入排序的不同之處在于拧额，它會優(yōu)先比較距離較遠(yuǎn)的元素，該方法因D.L.Shell于1959年提出而得名彪腔。
希爾排序的整體思想是將固定間隔的幾個元素之間排序侥锦，然后再縮小這個間隔。這樣到最后數(shù)列就成為了基本有序數(shù)列德挣，而前面我們講過插入排序對基本有序數(shù)列排序效果較好恭垦。
計算一個增量（間隔）值
對元素進(jìn)行增量元素進(jìn)行比較，比如增量值為7格嗅，那么就對0,7,14,21…個元素進(jìn)行插入排序
然后對1,8,15…進(jìn)行排序番挺，依次遞增進(jìn)行排序
所有元素排序完后，縮小增量比如為3屯掖，然后又重復(fù)上述第2玄柏，3步
最后縮小增量至1時，數(shù)列已經(jīng)基本有序懂扼，最后一遍普通插入即可
已知的最增量式是由 Sedgewick 提出的 (1, 5, 19, 41, 109,…)禁荸，該步長的項來自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 這兩個算式右蒲。這項研究也表明 "比較在希爾排序中是最主要的操作阀湿，而不是交換。 用這樣增量式的希爾排序比插入排序和堆排序都要快瑰妄，甚至在小數(shù)組中比快速排序還快陷嘴，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢。
def shell_sort(arr):
"""希爾排序"""
# 取整計算增量（間隔）值
gap = len(arr) // 2
while gap > 0:
# 從增量值開始遍歷比較
for i in range(gap, len(arr)):
j = i
current = arr[i]
# 元素與他同列的前面的每個元素比較间坐，如果比前面的小則互換
while j - gap >= 0 and current < arr[j - gap]:
arr[j] = arr[j - gap]
j -= gap
arr[j] = current
# 縮小增量（間隔）值
gap //= 2
return arr
比較性：排序時元素之間需要比較灾挨，所以為比較排序
穩(wěn)定性：因為希爾排序是間隔的插入邑退，所以存在相同元素相對順序被打亂，所以是不穩(wěn)定排序
時間復(fù)雜度：最壞時間復(fù)雜度O(n2)平均復(fù)雜度為O(n1.3)
空間復(fù)雜度：只需要常數(shù)個輔助單元劳澄，所以空間復(fù)雜度也為O(1)
記憶方法：插入排序是每輪都是一小步地技，希爾排序是先大步后小步，它第一個突破O(n2)的排序算法秒拔。聯(lián)想起阿姆斯特朗登月之后說：這是我個人一小步莫矗，卻是人類邁出的一大步。
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用作谚。歸并排序適用于子序列有序的數(shù)據(jù)排序。
從上圖看分解后的數(shù)列很像一個二叉樹庵芭。
使用遞歸將源數(shù)列使用二分法分成多個子列
申請空間將兩個子列排序合并然后返回
將所有子列一步一步合并最后完成排序
```python
def merge_sort(arr):
? ? """歸并排序"""
? ? if len(arr) == 1:
? ? ? ? return arr
? ? # 使用二分法將數(shù)列分兩個
? ? mid = len(arr) // 2
? ? left = arr[:mid]
? ? right = arr[mid:]
? ? # 使用遞歸運(yùn)算
? ? return marge(merge_sort(left), merge_sort(right))
def marge(left, right):
? ? """排序合并兩個數(shù)列"""
? ? result = []
? ? # 兩個數(shù)列都有值
? ? while len(left) > 0 and len(right) > 0:
? ? ? ? # 左右兩個數(shù)列第一個最小放前面
? ? ? ? if left[0] <= right[0]:
? ? ? ? ? ? result.append(left.pop(0))
? ? ? ? else:
? ? ? ? ? ? result.append(right.pop(0))
? ? # 只有一個數(shù)列中還有值妹懒，直接添加
? ? result += left
? ? result += right
? ? return result
```
比較性：排序時元素之間需要比較，所以為比較排序
穩(wěn)定性：我們從代碼中可以看到當(dāng)左邊的元素小于等于右邊的元素就把左邊的排前面双吆，而原本左邊的就是在前面眨唬，所以相同元素的相對順序不變，故為穩(wěn)定排序
時間復(fù)雜度：復(fù)雜度為O(nlog^n)
空間復(fù)雜度：在合并子列時需要申請臨時空間好乐，而且空間大小隨數(shù)列的大小而變化单绑，所以空間復(fù)雜度為O(n)
記憶方法：所謂歸并肯定是要先分解，再合并
今天給大家介紹的五種排序是比較簡單的排序曹宴，建議大家自己動手敲幾遍代碼搂橙，書讀百遍，其義自現(xiàn)笛坦。要求大家必須理解&記住它們的算法原理区转，因為代碼是永遠(yuǎn)記不住的，只要記住原理你就能用偽代碼實現(xiàn)版扩。 為了方便大家記憶我在每個算法分析最后給出了自己的記憶方法废离，如果你有不理解的地方，歡迎在下方留言礁芦，同時也歡迎大家轉(zhuǎn)發(fā)分享蜻韭！
