本博客的排序算法元素的排序順序默認(rèn)從小到大。

一. 冒泡排序–BubbleSort

基本思想：

兩兩比較相鄰記錄的元素，如果反序則交換，直到?jīng)]有反序的記錄。想象一下氣泡往上冒的過程，在往上冒的過程比較的是相鄰元素，最終會(huì)變成一個(gè)大氣泡（最后一個(gè)元素是最大的，如此類推）。

優(yōu)化后的冒泡排序

            
              def Bubble_Sort(lst):
	length = len(lst)
	for i in range(length,0,-1):
	flag = True
		for j in range(1,i):
			if lst[j-1] > lst[j]:
				lst[j-1], lst[j] = lst[j], lst[j-1]
				flag = False
	# 某一趟遍歷如果沒有數(shù)據(jù)交換，則說明已經(jīng)排好序了，因此不用再進(jìn)行迭代了
		if flag:
			break
	return lst

            
          

需要比較 $n(n?1)/2$ 次，并作等數(shù)量級的記錄移動(dòng)。因此總的時(shí)間復(fù)雜度是 $O(n^2)$ 。

二. 選擇排序–SelectionSort

基本思想：

通過n-i次的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)交換。

            
              def Selection_Sort(lst):
	length = len(lst)
	for i in range(length-1):
		min = i
		for j in range(i+1,length):
			if lst[min] > lst[j]:
				min = j
		if i != min:
			lst[i],lst[min] = lst[min],lst[i]  #這里才交換
	return lst

            
          

比較次數(shù)依然是 $n(n?1)/2$ 次，但是交換次數(shù)最好是交換0次，最差的時(shí)候也就 $n?1$ 次。但最終是比較與交換次數(shù)的總和，因此排序時(shí)間依然是 $O(n^2)$ 。

三. 插入排序–InsertionSort

基本思想：

將一個(gè)記錄插入到已經(jīng)排好序的有序表中。對于每個(gè)未排序的數(shù)據(jù)（可以認(rèn)為第一個(gè)元素是排好序的），在已排序的序列中從后向前掃描，找到相應(yīng)位置插入。沒錯(cuò)，這就是我們打撲克牌理牌時(shí)常用的排序手段。

1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果被掃描的元素（已排序）大于新元素，將該元素后移一位
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復(fù)步驟2~5

            
              def Inser_Sort(lst):
	length = len(lst)
	for i in range(1,length):
		tmp = lst[i]
		j = i
		while j>0 and lst[j-1] > tmp:
			lst[j] = lst[j-1]
			j -= 1
		lst[j] = tmp
	return lst

            
          

最好的情況，即本身就是有序的，例如：{2,3,4,5,6}，需比較n-1次，沒有移動(dòng)的記錄，時(shí)間復(fù)雜度為O(n);
最壞的情況，都是逆序，此時(shí)需比較 $2+3+...+n=(n+2)(n?1)/2$ 次，記錄移動(dòng)次數(shù)達(dá)到最大值。因此時(shí)間復(fù)雜度也是 $O(n^2)$ ，但是平均比較和移動(dòng)的次數(shù)約為 $n^2/4$ 次，性能比前兩種要好一些。

四. 希爾排序–ShellSort

基本思想:

希爾排序的實(shí)質(zhì)就是分組插入排序，該方法又稱縮小增量排序。
先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對全體元素進(jìn)行一次直接插入排序（此時(shí)增量=1，就是直接插入排序了）。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的。
代碼跟直接插入排序差不多：

            
              def Shell_Sort(lst):
	length = len(lst)
	gap = round(length/2)  #round 四舍五入 或 length//2
	while gap >= 1:
		for i in range(gap,length):
			mark = lst[i]
			j = i
			while j-gap>=0 and lst[j-gap] > mark;
				lst[j] = lst[j-gap]
				j -= gap
			lst[j] = mark
		gap = round(gap/2)
	return lst

            
          

希爾排序在第一輪循環(huán)后，較大的在后面而較小的在前面，也就是說基本讓整個(gè)序列基本有序了。 這其實(shí)就是希爾排序的精華所在，移動(dòng)記錄不是一步一步地挪動(dòng)，而是跳躍式地移動(dòng) 。最終在基本有序的情況下進(jìn)行直接插入排序，效率就很高了。時(shí)間復(fù)雜度為 $O(n^{\frac{3}{2}})$ 。另外由于記錄是跳躍式的移動(dòng)，希爾排序并不是一種穩(wěn)定的算法。

五. 堆排序–HeapSort

希爾排序是直接插入排序的改進(jìn)版，那么堆排序就是選擇排序的改進(jìn)版。選擇排序有一個(gè)缺點(diǎn)就是沒有把每一趟的比較結(jié)果記錄下來，在后一趟的比較中，有許多是比較是前一趟已經(jīng)做過了，但由于前一趟沒有保存比較結(jié)果，因?yàn)橛种貜?fù)執(zhí)行這些比較操作，比較次數(shù)較多。如果可以每次做到在每次選擇最小記錄的同時(shí)，并根據(jù)比較結(jié)果對其他記錄做出相應(yīng)調(diào)整，那么效率就會(huì)高很多。

堆的存儲：

基本思想：

將待排序的序列構(gòu)造成一個(gè)大頂堆。此時(shí)整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)。將它移走（就是將其與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值），將剩余的n-1個(gè)序列重新構(gòu)造一個(gè)堆，這樣就會(huì)得到n個(gè)元素中次大值。如此反復(fù)就得到一個(gè)有序序列。

步驟：

1. 先構(gòu)造最大堆：若數(shù)組下標(biāo)范圍為0~n，考慮到單獨(dú)一個(gè)元素是大根堆，則從下標(biāo)n/2開始的元素均為大根堆（葉子結(jié)點(diǎn)都可以認(rèn)為是大根堆）。于是只要從n/2-1開始，向前依次構(gòu)造大根堆，這樣就能保證，構(gòu)造到某個(gè)節(jié)點(diǎn)時(shí)，它的左右子樹都已經(jīng)是大根堆。
2. 堆排序：移除根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。第一次將heap[0]與heap[n-1]交換，再對heap[0]…h(huán)eap[n-2]做最大堆調(diào)整（忽略heap[n-1]，因?yàn)榇藭r(shí)他在未排序的堆中是最大的，所以heap[n-1]已經(jīng)是排好序了）。第二次將heap[0]與heap[n-2]交換，再對heap[0…n-3]做最大堆調(diào)整。重復(fù)該操作直至heap[0]和heap[1]交換。由于每次都是將最大的數(shù)并入到后面的有序區(qū)間，故操作完后整個(gè)數(shù)組就是有序的了。
3. 所以上面就有一個(gè)共用的函數(shù)–最大堆調(diào)整。

            
              def Heap_Sort(lst):
	#最大堆調(diào)整
	def Heap_Adujust(lst,start,end):
		root = lst[start]
		child = 2*start + 1
		while child
              
                < lst[child+1]: #是否有右孩子結(jié)點(diǎn)并且找最大值
				child = child + 1
			if root >= lst[child]:  #若父節(jié)點(diǎn)比最大的孩子結(jié)點(diǎn)要大，不做處理，跳出循環(huán)
				break
			#父節(jié)點(diǎn)比最大的孩子結(jié)點(diǎn)要小，交換
			lst[start] = lst[child]
			start = child
			child = 2*child + 1
		lst[start] = root

	length = len(lst)
	first = length//2-1
	#步驟一：構(gòu)造最大堆
	for i in range(first,-1,-1):
		Heap_Adjust(lst,i,length) 
	#步驟二：堆排序
	for i in range(length-1,-1,-1):
		lst[0],lst[i] = lst[i],lst[0] #根結(jié)點(diǎn)與最后一個(gè)交換 ，即將最大的往最后放
		Heap_Adjust(lst,0,i)
	return lst

              
            
          

在步驟一中，構(gòu)建堆的過程中，對于每個(gè)非終端節(jié)點(diǎn)，其實(shí)最多進(jìn)行兩次比較和互換操作，因此整個(gè)構(gòu)建堆的時(shí)間復(fù)雜度為O(n)；
在正式排序時(shí)，第i次取堆頂記錄重建需要用O(logi)的時(shí)間，需要取n-1次堆頂記錄，因此重建堆的時(shí)間復(fù)雜度為O(nlogn)。
總體來說，堆排序時(shí)間復(fù)雜度為O(nlogn)，最好，最壞和平均時(shí)間復(fù)雜度均為O(nlogn)，遠(yuǎn)比冒泡、選擇、直接插入的 $O(n^2)$ 好。由于記錄的比較和交換是跳躍進(jìn)行的，因此不穩(wěn)定。

六. 歸并排序–MergeSort

該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

基本思想：

所謂的歸并，是將兩個(gè)或兩個(gè)以上的有序文件合并成為一個(gè)新的有序文件，歸并排序是把一個(gè)有n個(gè)記錄的無序文件看成是由n個(gè)長度為1的有序子文件組成的文件，然后進(jìn)行兩兩歸并，如此重復(fù)，直至最后形成包含n個(gè)歸并，得到n/2個(gè)長度為2或者1的有序文件，再兩兩歸并，如此重復(fù)，直至最后形成包含n個(gè)記錄的有序文件位置，這種反復(fù)將兩個(gè)有序文件歸并成一個(gè)有序文件的排序方法稱為二路歸并排序。二路歸并排序的核心操作是將一堆數(shù)組中前后相鄰的兩個(gè)有序序列歸并為一個(gè)有序序列，如下圖所示：

使用非遞歸實(shí)現(xiàn)：

            
              def Merge_Sort(lst):

	#最底層的操作：將一層中 接連的兩個(gè)有序的列表合并成一個(gè)有序的列表
	#lfrom是源lst，lto是歸并到一個(gè)新的lst，low,mid,high分別是接連兩個(gè)有序列表的分段標(biāo)志位
	def merge(lfrom,lto,low,mid,high):
		i,j,k = low,mid,low
		while i
              
                < lfrom[j]:
				lto[k] = lfrom[i]
				i+=1
			else:
				lto[k] = lfrom[j]
				j+=1
			k+=1
			
        #因?yàn)榭赡軙?huì)出現(xiàn)lfrom中 lfrom[i...mid]的都比l[j...high]的都小或大
        # 或者 雙方其中一個(gè)的最后一個(gè)沒有歸并入lto
        # 所以出現(xiàn)以下兩種補(bǔ)歸并
        
		#將剩余的i到mid復(fù)制到lto
		while i
                
              
            
          

在一層中，歸并一對對分段需耗費(fèi)O(n)時(shí)間，由完全二叉樹的深度可知，整個(gè)歸并排序需進(jìn)行 $lo{g}_{2^n}$ （向上取整）次，因此，總的時(shí)間復(fù)雜度為O(nlogn)，這也是最好最壞、平均時(shí)間性能。空間復(fù)雜度因?yàn)?lto = [None]*llen ，所以空間復(fù)雜度是O(n)。由于記錄的移動(dòng)是相鄰的，所以算法穩(wěn)定。歸并排序雖占用內(nèi)存，但效率高并穩(wěn)定。

七. 快速排序–QuickSort

快速排序通常明顯比同為Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多筆試面試中能經(jīng)?？吹娇炫诺挠白印？梢娬莆湛炫诺闹匾?。

基本思想：

通過一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

步驟：

1. 從數(shù)列中挑出一個(gè)元素作為基準(zhǔn)數(shù)。
2. 分區(qū)過程，將比基準(zhǔn)數(shù)大的放到右邊，小于或等于它的數(shù)都放到左邊。
3. 再對左右區(qū)間遞歸執(zhí)行第二步，直至各區(qū)間只有一個(gè)數(shù)。
   

            
              def Quick_Sort(lst):
	#三數(shù)取中間值 保證取的樞軸不會(huì)是最值
	def partition(lst,low,high):
		mid = low+(high-low)//2
		if lst[low] > lst[high]:
			lst[low],lst[high] = lst[high],lst[low]
		if lst[mid] > lst[high]:
			lst[mid],lst[high] = lst[high],lst[mid]
		if lst[mid] > lst[low]:
			lst[low],lst[mid] = lst[mid],lst[low]

		key = lst[low]
		while low
              
                = key:
				high -= 1
			lst[low] = lst[high] #通過賦值的方式，而不是交換的方式，提高性能
			while low
                
                  <= key:
				low += 1
			lst[high] = lst[low]
			
		#此時(shí)low左右兩邊分別是小于和大于key的兩個(gè)區(qū)間
		lst[low] = key
		return low

	def sort(lst,low,high):
		if low
                  
                
              
            
          

遞歸樹深度 $lo{g}_{2^n}$ （向上取整），即僅需遞歸 $lo{g}_{2^n}$ 次，第一次需要做n次比較，第二次各自n/2次，如此類推，最優(yōu)情況下時(shí)間復(fù)雜度O(nlogn)；
最壞情況，序列為正序或逆序，遞歸樹畫出來就是一顆斜樹，因此需要比較n(n-1)/2次，時(shí)間復(fù)雜度為 $O(n^2)$ 。
平均來說，時(shí)間復(fù)雜度O(nlogn)；空間復(fù)雜度為O(logn)-O(n)（斜樹），平均空間復(fù)雜度為O(logn)。
關(guān)鍵字的比較和交換是跳躍進(jìn)行的，因此快排是一種不穩(wěn)定算法。

八. 對比

對于時(shí)間復(fù)雜度來說 ：堆排序和歸并排序發(fā)揮穩(wěn)定，快速排序就像個(gè)情緒化的天才，好的時(shí)候就極佳，差的時(shí)候就不行。但對于考題簡單（就是基本正序的序列），他們都算不過冒泡和插入。所以應(yīng)情況而使用排序算法。
對于空間復(fù)雜度 ：歸并排序強(qiáng)調(diào)馬跑得快就給馬喂飽，快速排序同樣發(fā)揮不穩(wěn)定，差的時(shí)候就是斜樹O(n)，好的時(shí)候就較好O(logn)（比歸并好）；其他算法只用一個(gè)輔助空間來進(jìn)行交換。所以在乎內(nèi)存使用量多少時(shí)，歸并和排序就不是一個(gè)很好的選擇。
對于穩(wěn)定性 ：如果非常在乎排序的穩(wěn)定性，那就選擇歸并比較好了。