本博客的排序算法元素的排序順序默認從小到大。

一. 冒泡排序–BubbleSort

基本思想：

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

優化后的冒泡排序

            
              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
	# 某一趟遍歷如果沒有數據交換，則說明已經排好序了，因此不用再進行迭代了
		if flag:
			break
	return lst

            
          

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

二. 選擇排序–SelectionSort

基本思想：

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

            
              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

            
          

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

三. 插入排序–InsertionSort

基本思想：

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

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描
3. 如果被掃描的元素（已排序）大于新元素，將該元素后移一位
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復步驟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次，沒有移動的記錄，時間復雜度為O(n);
最壞的情況，都是逆序，此時需比較 $2+3+...+n=(n+2)(n?1)/2$ 次，記錄移動次數達到最大值。因此時間復雜度也是 $O(n^2)$ ，但是平均比較和移動的次數約為 $n^2/4$ 次，性能比前兩種要好一些。

四. 希爾排序–ShellSort

基本思想:

希爾排序的實質就是分組插入排序，該方法又稱縮小增量排序。
先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（此時增量=1，就是直接插入排序了）。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的。
代碼跟直接插入排序差不多：

            
              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

            
          

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

五. 堆排序–HeapSort

希爾排序是直接插入排序的改進版，那么堆排序就是選擇排序的改進版。選擇排序有一個缺點就是沒有把每一趟的比較結果記錄下來，在后一趟的比較中，有許多是比較是前一趟已經做過了，但由于前一趟沒有保存比較結果，因為又重復執行這些比較操作，比較次數較多。如果可以每次做到在每次選擇最小記錄的同時，并根據比較結果對其他記錄做出相應調整，那么效率就會高很多。

堆的存儲：

基本思想：

將待排序的序列構造成一個大頂堆。此時整個序列的最大值就是堆頂的根結點。將它移走（就是將其與堆數組的末尾元素交換，此時末尾元素就是最大值），將剩余的n-1個序列重新構造一個堆，這樣就會得到n個元素中次大值。如此反復就得到一個有序序列。

步驟：

1. 先構造最大堆：若數組下標范圍為0~n，考慮到單獨一個元素是大根堆，則從下標n/2開始的元素均為大根堆（葉子結點都可以認為是大根堆）。于是只要從n/2-1開始，向前依次構造大根堆，這樣就能保證，構造到某個節點時，它的左右子樹都已經是大根堆。
2. 堆排序：移除根節點，并做最大堆調整的遞歸運算。第一次將heap[0]與heap[n-1]交換，再對heap[0]…heap[n-2]做最大堆調整（忽略heap[n-1]，因為此時他在未排序的堆中是最大的，所以heap[n-1]已經是排好序了）。第二次將heap[0]與heap[n-2]交換，再對heap[0…n-3]做最大堆調整。重復該操作直至heap[0]和heap[1]交換。由于每次都是將最大的數并入到后面的有序區間，故操作完后整個數組就是有序的了。
3. 所以上面就有一個共用的函數–最大堆調整。

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

	length = len(lst)
	first = length//2-1
	#步驟一：構造最大堆
	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] #根結點與最后一個交換 ，即將最大的往最后放
		Heap_Adjust(lst,0,i)
	return lst

              
            
          

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

六. 歸并排序–MergeSort

該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想：

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

使用非遞歸實現：

            
              def Merge_Sort(lst):

	#最底層的操作：將一層中 接連的兩個有序的列表合并成一個有序的列表
	#lfrom是源lst，lto是歸并到一個新的lst，low,mid,high分別是接連兩個有序列表的分段標志位
	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
			
        #因為可能會出現lfrom中 lfrom[i...mid]的都比l[j...high]的都小或大
        # 或者 雙方其中一個的最后一個沒有歸并入lto
        # 所以出現以下兩種補歸并
        
		#將剩余的i到mid復制到lto
		while i
                
              
            
          

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

七. 快速排序–QuickSort

快速排序通常明顯比同為Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多筆試面試中能經常看到快排的影子。可見掌握快排的重要性。

基本思想：

通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。

步驟：

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

            
              def Quick_Sort(lst):
	#三數取中間值 保證取的樞軸不會是最值
	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]
			
		#此時low左右兩邊分別是小于和大于key的兩個區間
		lst[low] = key
		return low

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

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

八. 對比

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