冒泡排序
思想
冒泡排序是一個(gè)簡單的排序算法，這個(gè)排序算法的核心之處在于每個(gè)相鄰的元素都進(jìn)行比較，如果不是按順序的形式，就交換彼此。這個(gè)算法不適用于大數(shù)據(jù)量的排序，因?yàn)樗钠骄鶗r(shí)間復(fù)雜度和最差時(shí)間復(fù)雜度都是O(n^2)。
下圖是一個(gè)沒有排序好的數(shù)組：
首先，冒泡排序會(huì)比較前面兩個(gè)數(shù)字，判斷他們哪個(gè)會(huì)更大些。
在我們的例子中，14 和 33 已經(jīng)是按照從小到大的順序排列的了。所以我們不需要對這兩個(gè)元素進(jìn)行操作。接下來我們比較33和27。
我們發(fā)現(xiàn)，33和27并不是按照從小到大的順序排列的，這兩個(gè)數(shù)字就需要交換。
交換后的新數(shù)組的排列形式如下所示：
這時(shí)，我們需要繼續(xù)比較 33 和 35。由于 35 大于 33，也就是從小到大的順序排列的，所以不需要交換。
最后，我們比較下兩個(gè)數(shù)，35 和 10
我們知道 35 和 10 并不是按照從小到大的順序排列的，需要交換
最終，我們會(huì)對這兩個(gè)數(shù)字進(jìn)行交換，然后一次循環(huán)結(jié)束，我們發(fā)現(xiàn)達(dá)到的效果是，最大的數(shù)在數(shù)組的最后。下一次再進(jìn)行冒泡排序的時(shí)候，就不需要對最后的元素比較了。
按照新的元素 14， 27， 33， 10。再次循環(huán)上面的過程，直到排序完成。
在第二次循環(huán)之后，這個(gè)數(shù)組的樣子應(yīng)該是：
第三次循環(huán)后的樣子：
第四次：
以上就是一個(gè)冒泡排序的過程。
python實(shí)現(xiàn)
# 冒泡排序
def maopao(array):
for i in range(len(array)):
for j in range(len(array)-i-1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
if __name__ == '__main__':
array = [1, 2, 5, 8, 4, 19, 30, 3, 7, 9]
maopao(array)
print(array)
插入排序
思想
插入排序，在插入排序中，會(huì)維護(hù)一個(gè)始終排好序的子序列。比如說，低值部分一直維護(hù)成為一個(gè)排序的序列。一個(gè)元素想要被插入到這個(gè)已經(jīng)排好序的子序列，就必須要找到屬于它的特定的位置，然后插入到那個(gè)位置。插入排序的時(shí)間復(fù)雜度依然是O(n^2)。
同樣， 我們使用一個(gè)沒有排序的數(shù)組來演示插入排序。
插入排序會(huì)比較前兩個(gè)元素，14 和 33.
我們發(fā)現(xiàn)，這兩個(gè)元素已經(jīng)是升序排列了，到目前為止，14已經(jīng)在排序序列內(nèi)了。
然后插入排序向前挪動(dòng)一個(gè)元素，比較 33 和 27
我們發(fā)現(xiàn)他們不是升序排列的，所以我們需要將他們排列成升序的形式。
交換33和27，然后27也要和之前已經(jīng)排好序的那一部分進(jìn)行比較，目前我們的排好序的序列只有14，而27比14大，所以不需要做交換。第二個(gè)元素添加進(jìn)排好序的序列后的圖片如下所示：
現(xiàn)在我們的排序序列中有的就是14和27，接下來需要比較的是33和10
發(fā)現(xiàn)不是升序排列，
將10 和 33 交換
此時(shí)還需要再次比較10和已經(jīng)排序的序列內(nèi)的元素，發(fā)現(xiàn)10比27小，
不是升序排列，交換10和27
再向前我們發(fā)現(xiàn)，14 和 10 也不是按照升序排列。
我們再次交換10和14，經(jīng)過這三次的循環(huán)，我們能夠得到一個(gè)有序的子序列：
這個(gè)過程持續(xù)下去，一直到所有的元素都被包含在這個(gè)子元素內(nèi)部。這樣就實(shí)現(xiàn)了將一個(gè)數(shù)組內(nèi)的數(shù)字排序的功能。
python實(shí)現(xiàn)
def InsertSort(arr):
for i in range(1, len(arr)):
for j in range(i-1, -1, -1):
if arr[i] < arr[j]:
arr[i], arr[j] = arr[j], arr[i]
i -= 1
else:
break
# 改進(jìn)版本
def InsertSort2(arr):
for i in range(len(arr)):
while i >= 1 and arr[i] < arr[i-1]:
arr[i], arr[i-1] = arr[i-1], arr[i]
i -= 1
if __name__ == '__main__':
arr = [9, 25, 6, 4, 29, 10, 23, 45, 7, 30, 12]
InsertSort(arr)
print(arr)
選擇排序
思想
選擇排序同樣是一個(gè)比較簡單的排序算法，這個(gè)算法也是要維護(hù)兩個(gè)部分的數(shù)組。第一個(gè)部分的數(shù)組是已經(jīng)排好序的數(shù)組，另一部分是沒有排好序的數(shù)組。初始的時(shí)候是排好序的部分是空，沒有排序的部分是整個(gè)數(shù)組。
選擇排序的主要的工作流程就是，在沒排好序的數(shù)組中，找到最小的那個(gè)值，然后和沒排好序的最左邊的那個(gè)數(shù)字進(jìn)行交換。這樣再將最左邊的那個(gè)元素納入到已經(jīng)排好序的那個(gè)隊(duì)列中，就能夠?qū)⑴藕眯虻男蛄性龃笠粋€(gè)元素，而沒排好序的序列減少一個(gè)元素。插入排序的時(shí)間復(fù)雜度依然是O(n^2)，不適合大量數(shù)據(jù)的排序。
再次應(yīng)用我們之前的那個(gè)沒有排序的數(shù)組來看選擇排序的過程。
一開始，沒排序的最左邊是14這個(gè)元素，然后尋找整個(gè)沒有排序的數(shù)組中哪個(gè)是最小的元素，發(fā)現(xiàn)是10這個(gè)元素
交換10和14，在交換之后，排序的序列就出現(xiàn)了，只有一個(gè)元素是10.
然后繼續(xù)選取沒有排序的數(shù)組的最左側(cè)，是33，然后尋找整個(gè)沒有排序的數(shù)組，發(fā)現(xiàn)最小的那個(gè)值是14。
我們將33和14交換位置，然后就完成了第二次循環(huán)。生成了包含兩個(gè)元素的有序數(shù)組，和剩下的無序數(shù)組
然后循環(huán)這個(gè)過程， 我們就得到了所有的數(shù)據(jù)都是有序數(shù)組，無序數(shù)組為空的情況。整個(gè)數(shù)組排序完成。
以上就是選擇排序的所有思想。
希爾排序
思想
希爾排序是一種高效的排序方式，它是基于插入排序的一種排序算法。它相比插入排序能夠有效的避免大量的移動(dòng)操作。
這種算法使用插入排序，只是比較的時(shí)候使用的是很遠(yuǎn)的數(shù)據(jù)進(jìn)行比較，然后將它們排序。這個(gè)比較遠(yuǎn)的距離是通過下面的計(jì)算式子得出的：
h = h * 3 + 1
這種算法的時(shí)間復(fù)雜度是 O(n^2) ~ O(n*log2n).
下面介紹這個(gè)希爾排序：
我們先通過之前的例子再次看下希爾排序的工作方式。首先是計(jì)算h的值，h是從1開始的，帶入上面的公式發(fā)現(xiàn)，h=4. 然后就發(fā)現(xiàn) 4 這個(gè)值小于數(shù)組長度 8.
然后繼續(xù)計(jì)算h的值，帶入上面的公式得出，h=13. 大于了數(shù)組的長度8.由此可知，我們的初始距離就應(yīng)該選擇4. 那么下面的數(shù)組就能夠被分成四組分別排序。{35, 14}, {33, 19}, {42, 27}, {10, 44}
然后就是比較每組內(nèi)的這兩個(gè)數(shù)，如果發(fā)現(xiàn)不是升序排列的，就交換這兩個(gè)數(shù)字。那么第一次交換以后的模樣應(yīng)該如下所示：
那下一次的h的值就是1了，所以我們按照間隔1分組，就會(huì)分成一組，那么就是按照上面的數(shù)組進(jìn)行插入排序，如下圖：
在上面的結(jié)束以后，我們發(fā)現(xiàn)，只用到了四次交換就完成了功能。
python實(shí)現(xiàn)
def ShellSort(arrList):
arrLen = len(arrList)
h = 1
while h < arrLen//3:
h = h * 3 + 1
while h >= 1:
for i in range(h, arrLen):
j = i
while j >= h and arrList[j] < arrList[j-h]:
arrList[j], arrList[j-h] = arrList[j-h], arrList[j]
j -= h
h = h // 3
if __name__ == '__main__':
arr = [5, 1, 8, 9, 23, 56, 3, 65, 4, 10, 30]
ShellSort(arr)
print(arr)
歸并排序
思想
歸并排序是用到了分治的思想，分治的思想是將一個(gè)大問題拆分成很多的小問題，然后再將已經(jīng)處理完成的小問題合并成整個(gè)的大問題。在這個(gè)過程中，大問題就得到了解決。在大數(shù)據(jù)方面的 Map-Reduce 就是這樣的分治的思想。
歸并排序首先將數(shù)組等分，然后排序等分后的數(shù)組，最后再將排好序的兩個(gè)數(shù)組合并成一個(gè)排好序的數(shù)組。歸并排序的時(shí)間復(fù)雜度是O(n log n)
為了能夠更好的理解歸并排序，我們來看下面的數(shù)組：
依然是上次我們用到的沒有排序的數(shù)組，上面總共有八個(gè)數(shù)字，等分后就會(huì)變成每組四個(gè)數(shù)字。這樣的等分一直持續(xù)到只剩下一個(gè)數(shù)字的情況。
由于還沒有將數(shù)組等分到只有一個(gè)元素的情況，所以我們繼續(xù)等分。
此時(shí)，每個(gè)分組中只有兩個(gè)數(shù)字，還是可以繼續(xù)等分。
在這個(gè)時(shí)候，等分結(jié)束。因?yàn)樗械姆纸M都只能分到這種程度，沒有數(shù)組還能繼續(xù)等分了。
然后我們將數(shù)組進(jìn)行倆倆合并，首先我們需要比較兩個(gè)數(shù)組中的每一個(gè)數(shù)據(jù)，然后將這些數(shù)據(jù)放入一個(gè)新的數(shù)組中，新數(shù)組就是有序的。這里比較的過程就是 14 和 33 是升序的，不需改變。27 和 10 是降序的，需要先放入10，再放入27. 35 和19也是降序的，需要先放入19， 再放入27. 最后，42 和 44 是升序的，不需改變。
再下一次將前兩個(gè)合并到一個(gè)數(shù)組中，后面兩個(gè)合并到一個(gè)數(shù)組中。過程是：前兩個(gè)數(shù)組合并，先判斷14 和 10，發(fā)現(xiàn) 14 要 大于10，所以在新生成的數(shù)組中將 10 寫在第一個(gè)位置上。然后比較14 和 27 發(fā)現(xiàn)14小，將 14 寫在新生成的數(shù)組的第二個(gè)位置。在比較33 和 27，發(fā)現(xiàn)27 小，將27寫在新生成的數(shù)組中。由于第二個(gè)數(shù)組寫入完成，所以將第一個(gè)數(shù)組的剩余部分寫入新生成的數(shù)組。第三組和第四組合并過程也是類似：19 vs. 42 => 19, 35 vs. 42 => 35, 一個(gè)結(jié)束另一個(gè)寫入剩余的部分=>42, 44
最后，經(jīng)過最終的merge操作，生成的數(shù)組就是下面的這個(gè)模樣：
python實(shí)現(xiàn)
def MergeSort(array):
arrlen = len(array)
# 將數(shù)組切分成兩部分
if arrlen <= 1:
return array
midindex = arrlen // 2
# 將數(shù)組進(jìn)行遞歸切分
leftarr = MergeSort(array[:midindex])
rightarr = MergeSort(array[midindex:])
# 對切分的數(shù)據(jù)進(jìn)行排序
resarry = MergeCore(leftarr, rightarr)
return resarry
def MergeCore(leftArray, rightArray):
# 定義左右數(shù)組指針
leftindex = 0
rightindex = 0
# 定義指針邊界
leftlen = len(leftArray)
rightlen = len(rightArray)
# 定義空數(shù)組
reslist = []
# 進(jìn)行排序:比較兩邊每一個(gè)數(shù)的大小,小的放入空數(shù)組內(nèi)
while leftindex < leftlen and rightindex < rightlen:
if leftArray[leftindex] < rightArray[rightindex]:
reslist.append(leftArray[leftindex])
leftindex += 1
else:
reslist.append(rightArray[rightindex])
rightindex += 1
# 將兩邊剩余的數(shù)組放置到新數(shù)組中
reslist.extend(leftArray[leftindex:])
reslist.extend(rightArray[rightindex:])
return reslist
if __name__ == '__main__':
array = [13, 4, 53, 8, 12, 48, 34, 1, 23, 6]
res = MergeSort(array)
print(res)
快速排序
思想
快速排序是一個(gè)非常高效的排序算法，目前的應(yīng)用非常廣泛， 同時(shí)也是面試的常客。學(xué)好快速排序，能夠?qū)φ业焦ぷ饔泻艽蟮膸椭Ｍ瑫r(shí)，也有很多面試題也會(huì)用到這種思想。
快速排序也是一種分治的思想，但是它于歸并算法更加好是因?yàn)闅w并算法會(huì)用到輔助數(shù)組，其空間復(fù)雜度是O(n). 而快速排序不需要用到新的數(shù)組空間，它的空間復(fù)雜度是O(1).
快速排序的核心是：選定一個(gè)值作為軸心值，然后將數(shù)組分成兩個(gè)部分，一部分是大于這個(gè)軸心值，另一部分是小于這個(gè)軸心值的。然后將這個(gè)軸心值前的部分繼續(xù)使用快速排序，將這個(gè)軸心值的后半部分繼續(xù)使用快速排序。直到指剩下了一個(gè)元素的時(shí)候是不需要交換的?？焖倥判蚍浅＿m用于大數(shù)據(jù)量的排序，因?yàn)樗炔徽加枚嘤嗟目臻g，又能達(dá)到時(shí)間復(fù)雜度是O(nlogn).
下面，快速排序的步驟：
第一步：選擇最大的index作為軸心
第二步：選擇兩個(gè)指分別指向最左邊左邊和除了軸心的最右邊。
第三步：兩個(gè)指針分別是left和right。左邊的只想低索引。右邊的指向高索引。
第四步：當(dāng)左邊的索引的值小于軸心，那就向右移動(dòng)索引。
第五步：當(dāng)右邊的索引的值大于軸心，那就向左移動(dòng)索引。
第六步：當(dāng)?shù)谒牟胶偷谖宀蕉疾环蠒r(shí)，交換彼此。
第七步：如果 left >= right, 那么left就是新的軸心的位置，將軸心與之交換。
python實(shí)現(xiàn)
def partition(array, leftIndex, rightIndex):
i = leftIndex - 1
for j in range(leftIndex, rightIndex):
if array[j] < array[rightIndex]:
array[j], array[i+1] = array[i+1], array[j]
i += 1
array[i+1], array[rightIndex] = array[rightIndex], array[i+1]
return i+1
def QuickSort(array, leftIndex=0, rightIndex=None):
if len(array) <= 1:
return array
if rightIndex == None:
rightIndex = len(array) - 1
if leftIndex < rightIndex:
# 尋找中間值,使用partition來得到數(shù)組的中間值,并將數(shù)組分治
pivot = partition(array, leftIndex, rightIndex)
QuickSort(array, leftIndex, pivot - 1)
QuickSort(array, pivot + 1, rightIndex)
if __name__ == '__main__':
array = [123,23,5,89,47,45,12,3,9,8,14,7]
QuickSort(array)
print(array)
