背景
按照相關(guān)排序算法的解釋，手動用Python實(shí)現(xiàn)了一遍，記錄一下。(部分代碼是摘自網(wǎng)上)
排序結(jié)果為從小到大。
安利一個學(xué)習(xí)算法的經(jīng)典網(wǎng)站：算法圖示
這個網(wǎng)站上有很多算法的動圖示例，還帶有操作步驟解釋，實(shí)在是居家旅行學(xué)習(xí)必備之網(wǎng)站。
冒泡排序
原理
冒泡排序的原理是將臨近的數(shù)字兩兩進(jìn)行比較，然后按照從小到大或者從大到小的順序進(jìn)行交換。
動圖如下：
步驟
主要步驟如下：
- 比較相鄰的前后二個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個數(shù)據(jù)交換。
- 按照1的方法對源數(shù)組的第0個數(shù)據(jù)到N-1個數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個數(shù)據(jù)就“升”到數(shù)組第N-1個位置（就是最后一個位置）。
- 設(shè)置N=N-1，如果N不為0就重復(fù)前面二步，如果N==0，那么就是將原數(shù)組所有的數(shù)都排序一遍，此時排序完成。
代碼實(shí)現(xiàn)
def bubble_sort(array):
length = len(array)
while length > 0:
for i in range(length - 1):
if array[i] > array[i + 1]:
array[i], array[i + 1] = array[i + 1], array[i]
length -= 1
return array
基本優(yōu)化
1.對于結(jié)束的條件，如果遍歷某一趟時，沒有發(fā)生任何交換，說明此時排序已經(jīng)完成，所以我們可以在程序中加上一個標(biāo)志量用來表示某趟是否發(fā)生交換。
代碼如下：
def bubble_sort_better(array):
length = len(array)
flag = False
while length > 0:
for i in range(length - 1):
if array[i] > array[i + 1]:
array[i], array[i + 1] = array[i + 1], array[i]
flag = True
else:
flag = False
if flag is False:
return array
length -= 1
return array
2.如果存在這樣的數(shù)組： 假設(shè)數(shù)組有100個數(shù)，但是只有前10個是無序的，后面90個是已經(jīng)排序完畢，且均大于前面10個數(shù)。這樣我們分析即可發(fā)現(xiàn)，第一趟遍歷的時候，最后發(fā)生交換的位置必定小于10。所以我們只需要記錄下這個最后的位置，下一次，只需要從頭遍歷到這個位置即可。
代碼如下：
def bubble_sort_best(array):
length = len(array)
while length > 0:
for i in range(length - 1):
if array[i] > array[i + 1]:
array[i], array[i + 1] = array[i + 1], array[i]
length = i + 1
length -= 1
return array
直接插入排序
原理
插入排序的基本思想就是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。
動圖效果如下：
步驟
設(shè)數(shù)組為a[0…n-1]。
- 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置中
- 重復(fù)步驟2
代碼實(shí)現(xiàn)
def insert_while(nums):
for index in range(1, len(nums)):
deal_num = nums[index]
j = index - 1
while j >= 0 and nums[j] > deal_num:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = deal_num
希爾排序
原理
希爾排序，也稱遞減增量排序算法，實(shí)質(zhì)是分組插入排序。由 Donald Shell 于1959年提出。希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高， 即可以達(dá)到線性排序的效率
- 但插入排序一般來說是低效的， 因為插入排序每次只能將數(shù)據(jù)移動一位
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行依次直接插入排序。
步驟
我們以一組數(shù)[49, 38, 65, 97, 26, 13, 27, 49, 55, 4]為例。
加入首先我們以步長5排序
49 38 65 97 26
13 27 49 55 4
然后我們對每列進(jìn)行排序。
13 27 49 55 4
49 38 65 97 26
合并變成了[13, 27, 49, 55, 4, 49, 38, 65, 97, 26]。第一輪結(jié)束。
更換步長為5//2=2,繼續(xù)排序
13 27
49 55
4 49
38 65
97 26
排序過后
4 26
13 27
38 49
49 55
97 65
合并：[4,26,13,27,38,49,49,55,97,65]
更換步長為2//1=1
排序之后就得到了結(jié)果。
代碼實(shí)現(xiàn)
def shell_sort(array, n):
step = 2
now_gap = n // step # 初始步長
while now_gap > 0:
for i in range(now_gap, n):
# 每個步長進(jìn)行插入排序
temp = array[i]
j = i
# 插入排序
while j >= now_gap and array[j - now_gap] > temp:
array[j] = array[j - now_gap]
j = j - now_gap
array[j] = temp
# 新的步長
now_gap //= step
return array
基本優(yōu)化
優(yōu)化部分主要在與步長的選擇上，請移步維基百科上查閱。
當(dāng)前比較優(yōu)秀的步長序列有：
-
已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，該序列的項來自
這兩個算式。這項研究也表明“比較在希爾排序中是最主要的操作，而不是交換。”用這樣步長序列的希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢。
- 另一個在大數(shù)組中表現(xiàn)優(yōu)異的步長序列是（斐波那契數(shù)列除去0和1將剩余的數(shù)以黃金分區(qū)比的兩倍的冪進(jìn)行運(yùn)算得到的數(shù)列）：(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)
直接選擇排序
原理
直接選擇排序和直接插入排序類似，都將數(shù)據(jù)分為有序區(qū)和無序區(qū)，所不同的是直接插入排序是將無序區(qū)的第一個元素直接插入到有序區(qū)以形成一個更大的有序區(qū)，而直接選擇排序是從無序區(qū)選一個最小的元素直接放到有序區(qū)的最后。
步驟
- 在給定的數(shù)組中找到最小(大)的元素，將其放置為數(shù)組的首位作為已排序區(qū)域。
- 繼續(xù)在剩下的數(shù)組區(qū)域中尋找最小(大)的元素，放置到已排序區(qū)域的后邊。
- 重復(fù)2步知道剩下的元素排序完畢。
動圖示例：
代碼實(shí)現(xiàn)
def select_sort(array):
for i in range(len(array)):
min_index = i
for j in range(i + 1, len(array)):
if array[j] < array[min_index]:
min_index = j
array[min_index], array[i] = array[i], array[min_index]
return array
歸并排序
原理
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。它的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
首先是合并兩個數(shù)組。思路如下：比較兩個數(shù)組的最前面的數(shù)字，取小的那個，取了之后就要從原來的數(shù)組中刪除這個數(shù)字。 然后繼續(xù)比較，知道一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復(fù)制過來即可。
再者考慮遞歸分解。思路如下：將數(shù)組分為left和right，如果這兩個數(shù)組內(nèi)部有序，就合并這兩個數(shù)組。確定兩個數(shù)組內(nèi)部有序的方法是，持續(xù)二分，知道每個小組中只有一個數(shù)字，此時該小組就認(rèn)為有序。然后合并相鄰兩個小組。
動圖演示：
代碼實(shí)現(xiàn)
def merge_array(array1, array2):
left_index = right_index = 0
result = []
# 循環(huán)比較兩個數(shù)組，知道某個數(shù)組為空
while len(array1) > left_index and len(array2) > right_index:
if array1[left_index] < array2[right_index]:
result.append(array1[left_index])
left_index += 1
else:
result.append(array2[right_index])
right_index += 1
# 將不為空數(shù)組剩下的數(shù)字依次加入到結(jié)果列表中。另一個是空列表，所以可以這樣實(shí)現(xiàn)。
result += array1[left_index:]
result += array2[right_index:]
return result
def divide_array(array):
# 結(jié)束條件
if len(array) <= 1:
return array
index = len(array) // 2
left = divide_array(array[:index]) # 左半部分
right = divide_array(array[index:]) # 右半部分
return merge_array(left, right)
快速排序
原理
快速排序通常明顯比同為Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多筆試面試中能經(jīng)?？吹娇炫诺挠白印？梢娬莆湛炫诺闹匾浴?/p>
步驟
- 先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。
- 分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
- 再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)
動圖示例：
代碼實(shí)現(xiàn)
# 普通實(shí)現(xiàn)
def quick_sort_simple(array):
if len(array) <= 1:
return array
key = array[0]
less, greater = [], []
for i in range(1, len(array)):
if array[i] > key:
greater.append(array[i])
else:
less.append(array[i])
return quick_sort_simple(less) + [key] + quick_sort_simple(greater)
# 使用列表推導(dǎo)式實(shí)現(xiàn)
def quick_sort_nic(array):
if len(array) <= 1:
return array
return quick_sort_nic([x for x in array if x < array[0]]) + [x for x in array if x == array[0]] + quick_sort_nic([x for x in array if x > array[0]])
# 不開辟空間實(shí)現(xiàn)
def quick_sort(ary):
return qsort(ary,0,len(ary)-1)
def qsort(ary,left,right):
#快排函數(shù)，ary為待排序數(shù)組，left為待排序的左邊界，right為右邊界
if left >= right : return ary
key = ary[left] #取最左邊的為基準(zhǔn)數(shù)
lp = left #左指針
rp = right #右指針
while lp < rp :
while ary[rp] >= key and lp < rp :
rp -= 1
while ary[lp] <= key and lp < rp :
lp += 1
ary[lp],ary[rp] = ary[rp],ary[lp]
ary[left],ary[lp] = ary[lp],ary[left]
qsort(ary,left,lp-1)
qsort(ary,rp+1,right)
return ary
堆排序
原理
堆排序與快速排序，歸并排序一樣都是時間復(fù)雜度為O(N*logN)的幾種常見排序方法，
首先我們要理解數(shù)據(jù)結(jié)構(gòu)中的二叉堆。具體介紹請移步文章數(shù)據(jù)結(jié)構(gòu)之堆。
我們知道二叉堆的兩大性質(zhì)：
- 父節(jié)點(diǎn)的鍵值總是大于或者等于任何一個子節(jié)點(diǎn)的鍵值。
- 每個節(jié)點(diǎn)的左右子樹都是一個二叉樹堆(都是最大堆或者是最小堆)
步驟
構(gòu)建最大堆(Build_Max_Heap):若數(shù)組下標(biāo)范圍為0~n，考慮到單獨(dú)一個元素的大根堆，則從下標(biāo)
n/2開始的元素均為大根堆。于是只要從n/2-1開始，向前依次構(gòu)造大根堆，這樣就保證，構(gòu)造到某結(jié)點(diǎn)時，它的左右子樹都已經(jīng)是大根堆。堆排序(HeapSort):由于堆是用數(shù)組模擬的。得到一個大根堆后，數(shù)組內(nèi)部并不是有序的。因此需要將堆化數(shù)組有序化。 這種操作的思想是：移除根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。第一次將
heap[0]與heap[n-1]交換，再對heap[0...n-2]做最大堆調(diào)整。第二次將heap[0]與heap[n-2]交換，再對heap[0..n-3]做最大堆調(diào)整。重復(fù)該操作直至heap[0]和heap[1]交換。由于每次都是將最大的數(shù)字并入到后邊的有序區(qū)間。所以操作完成時，整個數(shù)組就是有序的了。最大堆調(diào)整(Max_Heapify)：該方法是被調(diào)用的，目的是將堆的末端子結(jié)點(diǎn)作調(diào)整。使得子結(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)。
動圖演示：
代碼實(shí)現(xiàn)
def heap_sort(ary):
n = len(ary)
first = int(n / 2 - 1) # 最后一個非葉子節(jié)點(diǎn)
for start in range(first, -1, -1): # 構(gòu)造大根堆
max_heapify(ary, start, n - 1)
for end in range(n - 1, 0, -1): # 堆排，將大根堆轉(zhuǎn)換成有序數(shù)組
ary[end], ary[0] = ary[0], ary[end]
max_heapify(ary, 0, end - 1)
return ary
# 最大堆調(diào)整：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
# start為當(dāng)前需要調(diào)整最大堆的位置，end為調(diào)整邊界
def max_heapify(ary, start, end):
root = start
while True:
child = root * 2 + 1 # 調(diào)整節(jié)點(diǎn)的子節(jié)點(diǎn)
if child > end:
break
if child + 1 <= end and ary[child] < ary[child + 1]:
child = child + 1 # 取較大的子節(jié)點(diǎn)
if ary[root] < ary[child]: # 較大的子節(jié)點(diǎn)成為父節(jié)點(diǎn)
ary[root], ary[child] = ary[child], ary[root] # 交換
root = child
else:
break
相關(guān)代碼都放置在了我的github
參考資料：
