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



一般排序演算法

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

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

演算法最差時間複雜度最佳時間複雜度平均時間複雜度額外最差空間複雜度是否穩定應用場合
選擇排序
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)}}#
尾端遞迴:#{{O(\log 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}}#愈小愈適用。

特殊排序演算法

排名搜尋演算法

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

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

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

亂排演算法

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

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

演算法最差時間複雜度最佳時間複雜度平均時間複雜度額外最差空間複雜度是否穩定應用場合
Bogo排序
Bogo Sort
#{{O(\infty)}}##{{O(n)}}##{{O({n \times n!})}}##{{O(1)}}#排序者大概是猴子時。

Big-#{{O}}# 複雜度參考圖表

algorithm