冒泡排序（Bubble sort）
是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序算法的運(yùn)作如下：
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大（升序），就交換他們。
- 對(duì)每一個(gè)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
時(shí)間復(fù)雜度
- 最優(yōu)：O(n)（表示遍歷一次發(fā)現(xiàn)沒(méi)有任何可以交換的元素，排序結(jié)束。）
- 最壞：O(n2)
- 穩(wěn)定性：穩(wěn)定
def bubble_sort(alist):
"""冒泡排序"""
n = len(alist)
#for j in range(n-1,0,-1):
# for i in range(j):
for j in range(n-1):
# 記錄是否交換過(guò)
count = 0
for i in range(0, n - 1 - j):
# 班長(zhǎng)從頭走到尾
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
count += 1
if count == 0:
return
選擇排序（Selection sort）
是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
時(shí)間復(fù)雜度
- 最優(yōu)：O(n2)
- 最壞：O(n2)
- 穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）
def select_sort(alist):
"""選擇排序"""
n = len(alist)
for j in range(n-1): # j: 0 ~ n-2
min_index = j
for i in range(j+1, n):
if alist[min_index] > alist[i]:
min_index = i
alist[j], alist[min_index] = alist[min_index], alist[j]
插入排序（Insertion sort）
是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
時(shí)間復(fù)雜度
- 最優(yōu)：O(n)（升序排列，序列已經(jīng)處于升序狀態(tài)）
- 最壞：O(n2)
- 穩(wěn)定性：穩(wěn)定
def insert_sort(alist):
"""插入排序"""
n = len(alist)
# 從右邊的無(wú)序序列中取出多少個(gè)元素執(zhí)行這樣的過(guò)程
for j in range(1, n): # j : 1 ~ n-1
# i 代表內(nèi)層循環(huán)的起始值
i = j
# 執(zhí)行從右邊的無(wú)序序列中取出第一個(gè)元素，即i位置的元素，然后將其插入到前面的正確位置中
while i > 0:
if alist[i] < alist[i-1]:
alist[i], alist[i-1] = alist[i-1], alist[i]
i -= 1
else:
break
希爾排序（Shell sort）
是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序，隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
時(shí)間復(fù)雜度
- 最優(yōu)：O(n1.3)
- 最壞：O(n2)
- 穩(wěn)定性：不穩(wěn)定
def shell_sort(alist):
# n = 9
n = len(alist)
# gap = 4
gap = n // 2
# gap變化到0之前，插入算法執(zhí)行的次數(shù)
while gap > 0:
# 插入算法，與普通的插入算法的區(qū)別就是gap步長(zhǎng)
for j in range(gap, n):
# j = [gap, gap+1, gap+2, ..., n-1]
i = j
while i > 0:
if alist[i] < alist[i - gap]:
alist[i], alist[i - gap] = alist[i - gap], alist[i]
i -= gap
else:
break
gap //= 2
快速排序（Quick sort）
是對(duì)冒泡排序的一種改進(jìn)。通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
快速排序的基本思想是:
- 先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)
- 分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊
- 再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)
時(shí)間復(fù)雜度
- 最優(yōu)：O(nlogn)
- 最壞：O(n2)
- 穩(wěn)定性：不穩(wěn)定
def quick_sort(alist, first, last):
"""快速排序"""
# 遞歸退出條件
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
# high 左移
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
# low 右移
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
# 從循環(huán)退出時(shí)，low == high
alist[low] = mid_value
# 對(duì)low左邊的列表執(zhí)行快速排序
quick_sort(alist, first, low - 1)
# 對(duì)low右邊的列表執(zhí)行快速排序
quick_sort(alist, low + 1, last)
歸并排序（Merge sort）
是采用分治法的一個(gè)非常典型的應(yīng)用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
將數(shù)組分解最小之后，然后合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)，誰(shuí)小就先取誰(shuí)，取了后相應(yīng)的指針就往后移一位。然后再比較，直至一個(gè)數(shù)組為空，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過(guò)來(lái)即可。
時(shí)間復(fù)雜度
- 最優(yōu)：O(nlogn)
- 最壞：O(nlogn)
- 穩(wěn)定性：穩(wěn)定
def merge_sort(alist):
"""歸并排序"""
n = len(alist)
if n<= 1:
return alist
mid = n//2
# left 采用歸并排序后形成的有序的新的列表
left_li = merge_sort(alist[:mid])
# right 采用歸并排序后形成的有序的新的列表
right_li = merge_sort(alist[mid:])
# 將兩個(gè)有序的子序列合并為一個(gè)新的整體
left_pointer, right_pointer = 0, 0
result = []
while left_pointer < len(left_li) and right_pointer < len(right_li):
if left_li[left_pointer] <= right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer += 1
else:
result.append(right_li[right_pointer])
right_pointer += 1
result += left_li[left_pointer:]
result += right_li[right_pointer:]
return result
