寫程式的基本功：排序演算法(Sorting Algorithm)

這裡所稱的排序(Sorting)，是指將一串不規則的序列資料(如陣列資料)依照遞增或是遞減的方式重新編排。要將一串不規則的數值資料遞增或是遞減排列，方法當然不會只有一種，而不同方法排列資料的難易度、速度和其它特性自然也會有所不同。排序演算法(Sorting Algorithm)就是排列資料的方法，目前已知的方法有很多，在這篇文章中將會整理本站所介紹過的大部份排序演算法。

一般排序演算法

這邊所列表出來的演算法都是用來以遞增或遞減的方式排序一個序列。

以#{{n}}#來表示要排序的資料筆數。以#{{k}}#來表示要排序的資料可能的值的數量。以#{{m}}#來表示桶子的數量。

演算法	最差時間複雜度	最佳時間複雜度	平均時間複雜度	最差空間複雜度	是否穩定	應用場合
選擇排序 Selection Sort	#{{O(n^2)}}#	#{{O(n^2)}}#	#{{O(n^2)}}#	#{{O(1)}}#	否	不怎麼實用。
交換排序 Exchange Sort	#{{O(n^2)}}#	#{{O(n^2)}}#	#{{O(n^2)}}#	#{{O(1)}}#	否	不怎麼實用。
氣泡排序 Bubble Sort	#{{O(n^2)}}#	#{{O(n)}}#	#{{O(n^2)}}#	#{{O(1)}}#	是	當#{{n}}#很小時特別適用。
插入排序 Insertion Sort	#{{O(n^2)}}#	#{{O(n)}}#	#{{O(n^2)}}#	#{{O(1)}}#	是	當#{{n}}#很小時特別適用。也常用來加速快速排序法和合併排序法。
雞尾酒排序 Cocktail Sort	#{{O(n^2)}}#	#{{O(n)}}#	#{{O(n^2)}}#	#{{O(1)}}#	是	不怎麼實用。
希爾排序 Shell Sort	#{{O(n^2)}}#	#{{O(n \log n)}}#	?	#{{O(1)}}#	否	如果能找出最佳間距(gap)，是不錯的選擇；但若找不出最佳間距(gap)的話，就不怎麼實用。
合併排序 Merge Sort	#{{O(n \log n)}}#	#{{O(n \log n)}}#	#{{O(n \log n)}}#	#{{O(n)}}#	是	適用於大部分的場合。
快速排序 Quck Sort	#{{O(n^2)}}#	#{{O(n \log n)}}#	#{{O(n \log n)}}#	一般：#{{O(n)}}#	否	適用於大部分不需穩定排序的場合。
堆積排序 Heap Sort	#{{O(n \log n)}}#	#{{O(n)}}#	#{{O(n \log n)}}#	#{{O(1)}}#	否	不怎麼實用。
計數排序 Counting Sort	#{{O(n + k)}}#	#{{O(n + k)}}#	#{{O(n + k)}}#	原地：#{{O(k)}}# 非原地：#{{O(n + k)}}#	原地：否非原地：是	#{{k}}#愈小愈適用。
桶排序 Bucket Sort	#{{O(n^2)}}#	#{{O(n + m)}}#	#{{O(n + {{n^2} \over m} + m )}}#	不預先配置桶子的空間：#{{O(k)}}# 預先配置桶子的空間：#{{O(n + k)}}# 使用了其它需要額外空間的排序演算法：?	使用穩定排序法來排序每個桶子：是有使用到不穩定排序法：否	資料可以被有效雜湊時適用。
基數排序 Radix Sort	LSD：#{{O((n + k) \times d)}}# 穩定MSD：#{{O(n \times d)}}#	LSD：#{{O((n + k) \times d)}}# 穩定MSD：#{{O(n)}}#	LSD：#{{O((n + k) \times d)}}# 穩定MSD：#{{O(n \times d)}}#	LSD：#{{O(n + k)}}# 穩定MSD：#{{O((n + k) \times d)}}#	LSD：是穩定MSD：是 (原地MSD：否)	資料可以被快速切分為多鍵值時適用。

特殊排序演算法

排名搜尋演算法

在序列中快速找出第#{{K}}#小或是第#{{K}}#大的元素。

以#{{n}}#來表示要搜尋或排序的資料筆數。

演算法	最差時間複雜度	最佳時間複雜度	平均時間複雜度	最差空間複雜度	是否穩定	應用場合
快速選擇 Quickselect	#{{O(n^2)}}#	#{{O(n)}}#	#{{O(n)}}#	#{{O(1)}}#	是	想從序列中找出一個第K小或是第K大元素時。

亂排演算法

用很奇耙的作法，以遞增或遞減的方式排序一個序列。