排序算法在算法界是一個怎麼樣的存在？就好像在學術界中數學的地位，說直接用好像用不上，可是不會做起事情來總會捉襟見肘，左支右绌。找工作的時候，有的面試官甚至會讓我們手寫排序算法。既然排序算法如此重要，就讓我們一起去夯實基礎，切切實實得掌握它吧。
前言
先講兩個重要的概念。
1.所謂穩定排序就是指數組中相等的元素在排序過後前後順序不變。
2.排序算法的平均複雜度是有下限的，為nlog(n)。是以大家不要再想着能發明什麼牛逼的算法可以達到線性增長的。至于這個定理的證明，比較複雜，我會在下篇文章中專門講述。
冒泡算法
運動前總要熱身，防止拉傷，深入研究排序算法前，先給大家介紹一個最常見，算法思想最簡單最粗暴的排序算法——冒泡排序。
重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
def bubble_sort(original_array):
L = len(original_array)
for i in range(1, L):
for j in range(0, L - i):
if original_array[j] > original_array[j+1]:
original_array[j], original_array[j+1] = original_array[j+1], original_array[j]
冒泡排序.gif
對該算法進行複雜性分析。我首先取了100個數組，數組規模從1到1000個元素均勻遞增，數組中每個數的大小在(1,10000)，得到下圖。橫坐标是排序的數組規模大小，縱坐标是排序所用時間，機關為秒。以後的圖縱橫坐标都是如此。
bubble_figure_1.png
能夠看出來，随着數組元素規模越來越大，所耗費時間呈現螺旋式上升的趨勢。不過波動較大，我們也看不太清楚它是個怎麼樣的曲線。為此我擴大了樣本規模，請看下圖。
bubble_figure_2.png
從這張圖中我們可以很清晰明了的看出，這是個二次曲線。這也符合實際情況，冒泡排序的算法複雜度是數組規模的平方。
冒泡排序可以說是最經典的，最穩定的一個算法，上算法課的同學們一定會接觸它。因為它似乎是一把打開算法大門的鑰匙，有了它，我們開始知道何為算法。但是，在實際應用中，我們并不用它。
插入排序
大家都有一個經驗，打撲克的時候，我們都喜歡按大小順序來擺放撲克牌，其實我們每次打一把撲克都在進行一次插入排序。
顯而易見，撲克牌在我們手中，我們将牌插來插去非常簡單。可是這種操作在計算機記憶體空間中就相當費時。可以去想象，每當我們插入一個資料，比它大的資料元素将整體往後挪動以來達到給它空出記憶體空間的目的。（python中沒有指針，暫時不考慮連結清單，這也是python的劣勢之一）由此我們可以得出一個結論，插入排序适用于資料量較少，而且當大部分資料是有序的情況下。
當資料大部分有序的情況下，複雜度近似于O(n)，這非常了不起了。
圖檔發自簡書App
圖檔發自簡書App
直接（簡單）插入排序.gif
def insert_sort(original_array):
L = len(original_array)
for i in range(1, L):
for x in range(i-1, -1, -1):
if original_array[x] > original_array[x+1]:
original_array[x], original_array[x+1] = original_array[x+1],original_array[x]
insert_figure.png
如圖，表現在二次曲線周圍上下波動。
希爾排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因D.L.Shell于1959年提出而得名。
該排序算法也是個很有紀念意義的算法，它首次突破了當時排序算法複雜度的下線O(n2)。
希爾排序.gif
def shell_sort(original_array):
L=len(original_array)
gap = (int)(L/2)
while(gap>=1):
for i in range(gap, L):
for x in range(i-gap, -1, -gap):
if original_array[x]>original_array[x+gap]:
original_array[x], original_array[x+gap] = original_array[x+gap], original_array[x]
gap = (int)(gap/2)
shell_figure.png
shell_figure2.png
為了是大家相信，我連續跑了兩次，顯而易見，它并不像上面兩個算法一樣如此優美得符合二次曲線。其實它在N上的常系數是1.3。
簡單選擇排序
簡單選擇排序在本章描述的算法中是最慢，即使在最好的情況下（數組已經完全有序）他的時間複雜度依然需要二次方時間。可以說，它是個“很笨”的算法，從每一次周遊疊代中都不會學到什麼。
(簡單）選擇排序.gif
def select_sort(original_array):
L = len(original_array)
for i in range(0, len(original_array)):
minimum = original_array[i]
for x in range(i+1, L):
if original_array[x] < minimum:
original_array[x], minimum = minimum, original_array[x]
original_array[i] = minimum
select_figure.png
對于該算法不再闡述過多細節，因為沒有什麼好說的。
堆排序
現在我們看看堆排序，這個算法展示了如何高效地應用選擇排序背後隐藏的原理。
世界杯将要來臨，我們都知道世界杯有小組賽，淘汰賽。小組賽需要和小組内每個隊伍比一場，而淘汰賽則是輸了就回家。我想沒有什麼比這兩種賽制更形象得來表述簡單選擇排序和堆排序的差別了。
當進入世界杯淘汰賽(32支隊伍)，每一隻隊伍都必須連續赢得六場比賽才可以進軍決賽。而很巧的是，log(32)=5，這讓我們聯想到了什麼？
沒錯，就是二叉樹。
該算法由1991年的計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發明。
步驟有三步。
圖檔發自簡書App
圖檔發自簡書App
1.以原始數組為基礎，建立最大堆(每個根節點上的值都不小于其左右子節點上的值)
2.經過第一步之後，該二叉樹的根節點已經是為該數組的最大值了。将該根節點與二叉樹末端子節點置換，然後将置換的該子節點從該二叉樹中删除，這樣最大值拍到了最後。
3.得到已經删除最末端子節點的二叉樹，重複步驟2，直至二叉樹僅僅剩下根節點，也就是最小值。
需要注意的是，數組是從0開始索引，是以該算法實作時容易在索引上出錯
堆排序.gif
def adjust_max_heap(original_array, L, i):
left = 2*i + 1
right = 2*i + 2
largest = i
if (leftoriginal_array[largest]):
largest = left
if (rightoriginal_array[largest]):
largest = right
if (largest!=i):
original_array[i], original_array[largest] = original_array[largest], original_array[i]
adjust_max_heap(original_array, L, largest)
def build_max_heap(original_array):
L= len(original_array)
for x in range((int)((L-2)/2), -1, -1):
adjust_max_heap(original_array, L, x)
#堆排序
def heap_sort(original_array):
flag = 1
build_max_heap(original_array)
L = len(original_array)
for i in range(L-1, -1, -1):
flag = flag + 1
original_array[0], original_array[i] = original_array[i], original_array[0]
adjust_max_heap(original_array, i, 0)
i = i - 1
heap_figure.png
可以看出來，速度非常快，而且幾乎是線性的。當然，它不是線性的，它是O(nlogn)。
快速排序
快速排序（Quicksort）是對冒泡排序的一種改進。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是，通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。
快速排序.gif
def quick_sort(original_array, start, end):
if start < end:
i,j,pivot = start, end, original_array[start]
while(i
while(i= pivot):
j = j - 1
if(i
original_array[i] = original_array[j]
i = i + 1
while(i
i = i + 1
if(i
original_array[j] = original_array[i]
j = j - 1
original_array[i] = pivot
quick_sort(original_array, start, i-1)
quick_sort(original_array, i+1, end)
quick_figure.png
在最壞情況下，其時間複雜度退化成二次方，但在平均情況下，其效果和堆排序一樣好。
基數排序
給大家介紹一種比較巧妙的排序。看圖便知其思路，獨辟蹊徑。
基數排序.gif
def radix_sort_nums(L):
maxNum = L[0]
for x in L:
if maxNum < x:
maxNum = x
times = 0
while (maxNum > 0):
maxNum = (int)(maxNum/10)
times = times+1
return times
def get_num_pos(num,pos):
return ((int)(num/(10**(pos-1))))%10
def radix_sort(L):
count = 10*[None]
bucket = len(L)*[None]
for pos in range(1,radix_sort_nums(L)+1):
for x in range(0,10):
count[x] = 0
for x in range(0,len(L)):
j = get_num_pos(int(L[x]),pos)
count[j] = count[j]+1
for x in range(1,10):
count[x] = count[x] + count[x-1]
for x in range(len(L)-1,-1,-1):
j = get_num_pos(L[x],pos)
bucket[count[j]-1] = L[x]
count[j] = count[j]-1
for x in range(0,len(L)):
L[x] = bucket[x]
radix_figure.png
歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序.gif
def mergearray(L,first,mid,last,temp):
i,j,k = first,mid+1,0
while (i <= mid) and (j <= last):
if L[i] <= L[j]:
temp[k] = L[i]
i = i+1
k = k+1
else:
temp[k] = L[j]
j = j+1
k = k+1
while (i <= mid):
temp[k] = L[i]
i = i+1
k = k+1
while (j <= last):
temp[k] = L[j]
j = j+1
k = k+1
for x in range(0,k):
L[first+x] = temp[x]
def merge_sort(L,first,last,temp):
if first < last:
mid = (int)((first + last) / 2)
merge_sort(L,first,mid,temp)
merge_sort(L,mid+1,last,temp)
mergearray(L,first,mid,last,temp)
def merge_sort_array(L):
temp = len(L)*[None]
merge_sort(L,0,len(L)-1,temp)
merge_figure.png
總結
圖檔發自簡書App
圖檔發自簡書App
從算法複雜性分析的圖得知，當資料量較大時，快速排序、堆排序、歸并排序、基數排序的速度都很快。其中快速排序無疑是速度最快的，當然它存在一個問題，當疊代次數再次擴大許多時，它的遞歸便存在問題，這涉及到快速排序的深度優化，以後會給大家講解。
而當資料量較小，尤其是原始數組大部分情況下本來就是有序的情況下，插入排序是最佳選擇。