排序是演算法最基本內容。
當初給我這樣印象似乎是網路上某篇文章,雖然已經找不到來源,
但隨著瞄過《算法導論》以及上過大學演算法後,這個想法深植心中。
那時學校作業好像只要求實作兩種排序並比較速度,
基於興趣,我實作了許多排序。
當時未收入睡眠排序;且初次實作大量排序,程式碼品質似乎欠佳。
測資
本篇所有的程式全都是「由小到大」排序,
另外對於所有程式碼的函數,你可以預設存在這樣一筆測資:
1 2 3 4 5 6 7 8
| ... int len = 5; int *arr = new int[5]; for(int i = 0; i < len; i++) arr[i] = rand() % 100; ... sort(arr, len); ...
|
陣列大小設定為變數不是所有編譯器都支援,故此採用動態宣告。
Bubble Sort
中文為「氣泡排序」
應該是最容易理解的排序之一,同時程式設計課程幾乎都會提及,
以 C 語言初學者來說,不熟練 STL 與其他排序時,會用上的排序技巧。
大致上的想法是,掃描陣列的兩個值,
保持兩個值一前一後,如果出現前值大於後值,則交換兩個值。
實作
筆者在這裡致歉,舊版文章的 Bubble sort 沒有符合相鄰元素才交換的要件;使得程式碼更接近插入排序,在後續 Odd-Even Sort 會造成理解困難,特此聲明。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| ...
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } ...
void bubble_sort(int *arr, int len) { for(int i = 0; i < len; i++) for(int j = i + 1; j < len; j++) if(arr[j-1] > arr[j]) swap(&arr[j-1], &arr[j]); } ...
|
可以發現 i
最小為 0,而 j
最小為 i+1
即 1,可以推得 j-1
最小為 0 不會超出邊界。
Selection Sort
中文為「選擇排序」
選擇排序是很直觀的一種排序,可以視作氣泡排序的加強版,
雖然概念很簡單,但註標的設定對於初學者來說是有可能混亂的。
原先氣泡排序要不斷地交換陣列的元素,
選擇排序提供了一種思路:「找到最小的交換」取代了「每次比較的交換」。
與氣泡排序相同,要掃描兩個值,
但這次將前值固定,後值從未排序的元素中選擇最小的跟前值換。
(未排序的陣列包含前值那個位置)
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| ...
void selection_sort(int *arr, int len) { for (int i = 0; i < len; i++) { int min = i; for (int j = i + 1; j < len; j++) if (arr[min] > arr[j]) min = j; swap(&arr[i], &arr[min]); } } ...
|
交換函數 (swap) 於前面段落有提及,有需要請參考 氣泡排序
Insertion Sort
中文為「插入排序」
插入排序是《算法導論》起初就介紹的排序方法。
概念其實很容易,就像是在玩撲克牌,
如果你整理你的手牌,你會把需要整理的牌取出,
然後一張張挪動比他大的牌,直到找到插入的位置。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| ...
void insertion_sort(int *arr, int len) { int i, j; for (i = 0; i < len; i++) { int tmp = arr[i]; for (j = i; j > 0 && tmp < arr[j - 1]; j--) arr[j] = arr[j - 1]; arr[j] = tmp; } } ...
|
Cocktail Sort
中文為「雞尾酒排序」
可以視為氣泡排序的加強版,氣泡排序從單邊處理;
而雞尾酒的想法是從陣列的兩端,像在搖瓶子那樣把兩頭逐漸處理完。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| ...
void cocktail_sort(int *arr, int len) { int left = 0; int right = len - 1; while (left < right) { for (int j = left; j < right; j++) if (arr[j] > arr[j + 1]) swap(&arr[j], &arr[j + 1]); right--; for (int j = right; j > left; j--) if (arr[j] < arr[j - 1]) swap(&arr[j], &arr[j - 1]); left++; } } ...
|
交換函數 (swap) 於前面段落有提及,有需要請參考 氣泡排序
Comb Sort
中文為「梳排序」
梳排序意思就是「梳子排序」借用了梳子的想法。
與氣泡排序一樣,每次掃描兩個元素,
但每次掃描的當下,掃描的元素距離是固定的,
並隨著每次掃描,寬度逐漸縮小。
就像是梳理凌亂的頭髮,
一開始會用齒距大的梳子,後來越用越小,
當然也會越來越整齊了。
實作
1 2 3 4 5 6 7 8 9 10
| ...
void comb_sort(int *arr, int len) { for (int width = len - 1; width > 0; width--) for (int begin = 0; (begin + width) < len; begin++) if (arr[begin] > arr[begin + width]) swap(&arr[begin], &arr[begin + width]); } ...
|
交換函數 (swap) 於前面段落有提及,有需要請參考 氣泡排序
Gnome Sort
中文為「地精排序」
這個排序特別的地方在於,實作出來往往只有一層迴圈結構,
大量交換元素使的整體類似氣泡排序,不是實用的算法。
具體來說,它透過進入未排序的範圍,
透過相鄰的兩兩交換,把元素換到正確的位置上。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| ...
void gnome_sort(int *arr, int len) { int i = 0; while (i < (len - 1)) { if (arr[i] <= arr[i + 1]) i++; else { swap(&arr[i], &arr[i + 1]); i--; } if (i < 0) i = 0; } } ...
|
交換函數 (swap) 於前面段落有提及,有需要請參考 氣泡排序
Odd-Even Sort
中文為「奇偶排序」,跟氣泡排序類似的排序算法。
排序的特性會透過排序奇數位的元素及偶數位的元素,來達成整體的排序,
實際上是氣泡排序的平行化版本,在 SIMD (Single-Instruction Multiple-Data) 的假設下,可以壓到 O(n)。
實作
這裡僅實做序列版:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| ...
void ood_even_sort(int *arr, int len) { bool sorted = false; while (sorted == false) { sorted = true; for (int base = 0; base < 2; base++) for (int i = base; i < (len - 1); i += 2) if (arr[i] > arr[i + 1]) { swap(&arr[i], &arr[i + 1]); sorted = false; } } } ...
|
Shell Sort
中文為「希爾排序」
可以看成是插入排序的加強版。
實作上,將固定間距的數字先做插入排序,
然後使間距逐漸遞減。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| ...
void shell_sort(int *arr, int len) { for (int gap = len; gap > 0; gap /= 2) for (int shift = 0; shift < gap; shift++) { int i, j; for (i = shift; i < len; i += gap) { int tmp = arr[i]; for (j = i; tmp < arr[j - gap] && j > shift; j -= gap) arr[j] = arr[j - gap]; arr[j] = tmp; } } } ...
|
Bucket Sort
中文為「桶子排序」
這是一個混合式的方法,必須先將元素分配到不同的桶子,
然後再將每個桶子內排序完成,最後再組合起來。對於平行系統似乎是個好選擇。
如果還記得複雜度分析的方法:
當 $c$ 為一常數,且 $n > n_{0}$ 時,
存在 $f(n) < cg(n)$ 這樣的關係,
可以表示為 $f(n) = O(g(n))$
也就是說,桶子排序的排序算法,
可以選擇一些 $n$ 在 $n_{0}$ 之下,速度很快的方法。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| ...
void bucket_sort(int *arr, int len) { int **bucket = new int*[10]; for (int i = 0; i < 10; i++) { bucket[i] = new int[len]; bucket[i][0] = 0; } for (int i = 0; i < len; i++) for (int j = 0; j < 10; j++) if (arr[i] >= j * 10 && arr[i] < (j + 1) * 10) bucket[j][1 + bucket[j][0]++] = arr[i]; for (int i = 0; i < 10; i++) insertion_sort(&bucket[i][1], bucket[i][0]); int index = 0; for (int i = 0; i < 10; i++) for (int j = 0; j < bucket[i][0]; j++) arr[index++] = bucket[i][j + 1]; delete[] bucket; } ...
|
注意桶子的大小跟數量,分配需要涵蓋到所有元素。事先知道資料分布情況是很有幫助的。
不要忘記使用 delete 與 delete[] 來清理記憶體空間。
Counting Sort
中文為「計數排序」
非比較排序,所以不受上限 $\Omega(nlg(n))$ 的限制。
大致上的概念是說,數數看有哪些元素,
比方說有 5 則在 5 號箱子加一,最後再整合蒐集來的資訊。
通常情況下很浪費空間,但速度相當快,
對於位數相當敏感,而非個數,所以也可將 $n$ 視為元素位數。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| ...
void counting_sort(int *arr, int len) { int *count = new int[99]; for (int i = 0; i < 99; i++) count[i] = 0; for (int i = 0; i < len; i++) count[arr[i]]++; int index = 0; for (int i = 0; i < 99; i++) for (int j = 0; j < count[i]; j++) arr[index++] = i; delete count; } ...
|
Radix Sort
中文為「基數排序」
基數排序是很特別的排序算法,
依照元素的每個位數排好,最終結果就會是排好的元素。
實作
縱使算法看起來要將元素顛三倒四,
但實作上有非常精巧的方法,
透過記錄元素位數的偏移量來將元素放置到正確的位置上。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| ... #include <cmath> ...
int get_digit(int number, int digit) { int a = (int) pow(10, digit); int b = (int) pow(10, digit - 1); number = number % a / b; return (int) floor(number); }
int get_max_number(int *arr, int len) { int number = -1; for (int i = 0; i < len; i++) if (number < arr[i]) number = arr[i]; return number; }
void radix_sort(int *arr, int len) { int max_number = get_max_number(arr, len); int max_digit = (int) ceil(log10(max_number)); int *tmp = new int[len]; int index[11]; int count[11]; for (int i = 1; i <= max_digit; i++) { for (int j = 0; j < 10; j++) count[j] = 0; for (int j = 0; j < len; j++) count[get_digit(arr[j], i)]++; index[0] = 0; for (int j = 0; j < 10; j++) index[j + 1] = index[j] + count[j]; for (int j = 0; j < len; j++) tmp[index[get_digit(arr[j], i)]++] = arr[j]; for (int j = 0; j < len; j++) arr[j] = tmp[j]; } delete tmp; } ...
|
注意引入 cmath 或 math.h 標頭檔,以便使用 ceil、log 與 pow 函數。
Merge Sort
中文為「合併排序」
重要的排序算法,同時也是排序問題最佳算法之一,
因為很容易解釋 $O(nlg(n))$ 的關係,似乎常被拿來當教材。
跟快速排序是相對的存在,且被大量函式庫實作:
使用案例 |
排序演算法 |
Perl 5.8 Default |
合併排序 |
Linux Kernel(linked list) |
合併排序 |
Java Arrays.sort() |
Tim Sort(源於合併與插入排序) |
Python Default |
Tim Sort(源於合併與插入排序) |
GNU Octave |
Tim Sort(源於合併與插入排序) |
實作
下面是遞迴的實作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| ...
void merge(int *arr, int *arr1, int *arr2, int len, int len1, int len2) { int index1 = 0; int index2 = 0; for (int i = 0; i < len; i++) { if (index1 == len1) arr[i] = arr2[index2++]; else if (index2 == len2) arr[i] = arr1[index1++]; else if (arr1[index1] < arr2[index2]) arr[i] = arr1[index1++]; else arr[i] = arr2[index2++]; } } ...
void merge_sort(int *arr, int len) { if (len > 1) { int left_len = len / 2; int right_len = len - left_len; int *left = new int[left_len]; int *right = new int[right_len]; for (int i = 0; i < left_len; i++) left[i] = arr[i]; for (int i = left_len; i < len; i++) right[i - left_len] = arr[i]; merge_sort(left, left_len); merge_sort(right, right_len); merge(arr, left, right, len, left_len, right_len); delete left; delete right; } } ...
|
如果合併函數不使用原始陣列的位置操作,而是另外建立空間,則需要回傳指標。
從觀察遞迴的版本可以發現,每次都是由 2 個元素(或 1 個)開始組合,
然後逐漸變成 4 個、8 個慢慢增加,正因為排序的關鍵在於合併,
也許可以透過迴圈模擬遞迴的過程。
下面是非遞迴的實作,使用了同樣的合併函數(參考上面):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| ...
int clamp(int number, int lower_bound, int upper_bound) { if (number > upper_bound) return upper_bound; if (number < lower_bound) return lower_bound; return number; } ...
void merge_sort(int *arr, int len) { int sub_len = 2; while (sub_len <= len * 2) { for (int i = 0; i < len; i += sub_len) { int left_len = sub_len / 2; int right_len = sub_len - left_len; int *left = arr + i; int *right = left + left_len; left_len = clamp(left_len, 0, (arr + len) - left); right_len = clamp(right_len, 0, (arr + len) - right); int *sub_arr = new int[sub_len]; merge(sub_arr, left, right, sub_len, left_len, right_len); for (int j = 0; j < sub_len; j++) arr[i + j] = sub_arr[j]; delete sub_arr; } sub_len *= 2; } } ...
|
Quick Sort
中文為「快速排序」
快速排序可以說是最重要的排序算法,
有著 $O(nlg(n))$ 的複雜度,但平均情況下又勝過其他排序。
實作
以下是遞迴版本:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| ...
void quick_sort(int *arr, int len) { if (len > 1) { int *pivot = arr; int *left = arr + 1; int *right = arr + len - 1; while (left < right) { while (*left < *pivot && left < right) left++; while (*right >= *pivot && left < right) right--; if (left < right) swap(left, right); } if (*left < *pivot) swap(pivot, left); int *start = arr; int *end = arr + len; int *center = left; quick_sort(start, center - start); quick_sort(center, end - center); } } ...
|
也可以使用堆疊模擬這個過程,下面是非遞迴版本的快速排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| ... #include <stack> #include <utility> ...
void quick_sort(int *arr, int len) { pair<int*, int*> index; stack<pair<int*, int*>> stack; if (len <= 1) return; stack.push(make_pair(arr, arr + len - 1)); while (!stack.empty()) { index = stack.top(); stack.pop(); int *pivot = index.first; int *left = index.first + 1; int *right = index.second; while (left < right) { while (*left < *pivot && left < right) left++; while (*right >= *pivot && left < right) right--; if (left < right) swap(left, right); } if (*left < *pivot) swap(pivot, left); int *center = left; if (index.first < center - 1) stack.push(make_pair(index.first, center - 1)); if (center < index.second) stack.push(make_pair(center, index.second)); } } ...
|
注意引入 stack 或 utility 標頭檔,以便使用 stack 及 pair 物件。
快速排序的實作有很多細節,可以先在紙上模擬這些步驟以利實作。
Binary Search Tree
中文為「二元搜尋樹」
利用二元樹資料結構的排序方法。
事實上,只要建立一個二元搜尋樹後,
使用中序走訪便可以得到排序完成的結果。
實作
實作時,可以建立先「二元搜尋樹」的類別並實作方法。
下面是二元搜尋樹節點的類別:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| ...
class BinaryTreeNode { public: BinaryTreeNode(int data); int data; BinaryTreeNode *left; BinaryTreeNode *right; };
BinaryTreeNode::BinaryTreeNode(int data) { this->data = data; this->left = nullptr; this->right = nullptr; } ...
|
雖然有實作過完整的二元樹,
但其實排序功能其實不需要太多的方法。
由於實際上外部調用不需要知道樹根的指標,
實作上可以透過重載函數的方法隱藏起來,
另外取回排序過的值時,傳入陣列的開頭利用註標及中序走訪依序取回。
下面是二元樹的類別:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| class BinaryTree { public: BinaryTree(); void push(int data); void gain(int *arr); private: BinaryTreeNode *root; void push(BinaryTreeNode *root, int data); void traversal(BinaryTreeNode *root, int *arr); int index; };
BinaryTree::BinaryTree() { this->root = nullptr; }
void BinaryTree::push(int data) { this->push(this->root, data); }
void BinaryTree::gain(int *arr) { this->index = 0; this->traversal(this->root, arr); }
void BinaryTree::push(BinaryTreeNode *root, int data) { if (this->root == nullptr) this->root = new BinaryTreeNode(data); else if (root->data > data) { if (root->left == nullptr) root->left = new BinaryTreeNode(data); else this->push(root->left, data); } else { if (root->right == nullptr) root->right = new BinaryTreeNode(data); else this->push(root->right, data); } }
void BinaryTree::traversal(BinaryTreeNode *root, int *arr) { if (root != nullptr) { if (root->left != nullptr) traversal(root->left, arr); arr[this->index] = root->data; this->index++; if (root->right != nullptr) traversal(root->right, arr); } }
|
調用的時候就相當簡單了:
1 2 3 4 5 6 7 8 9 10
| ...
void binary_tree_sort(int *arr, int len) { BinaryTree tree; for (int i = 0; i < len; i++) tree.push(arr[i]); tree.gain(arr); } ...
|
存在許多封裝資料結構的設計方法;
然而這裡的這個方法存在一個瑕疵,當儲存的節點數目跟陣列大小不符時會出錯,
但待排序的內容為串列結構時,可能很適合這樣的二元樹排序技巧。
Heap Sort
中文為「堆積排序」
堆積是完全二元樹,雖然是二元樹但性質與二元搜尋樹不同。
作為排序算法使用時,是借助本身的特性來使用,
是速度非常快的排序算法。
堆積通常使用陣列模擬,而且第 0 個位置通常不用。
實作
傳統的做法,主要圍繞在建立堆積與取出堆積資料兩個步驟。
在建立堆積時,先將資料放在樹葉節點上,然後向上調整;
取出資料時,將樹根與樹葉節點交換,然後裁取樹葉。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| ...
void heap_sort(int *arr, int len) { int *heap = new int[len + 1]; for (int i = 0; i < len + 1; i++) heap[i] = 0; int leaf = 1; for (int i = 0; i < len; i++) { heap[leaf] = arr[i]; int tmp = leaf; while (heap[tmp / 2] > heap[tmp]) { swap(&heap[tmp / 2], &heap[tmp]); tmp /= 2; } leaf++; } leaf -= 1; for (int i = 0; i < len; i++) { swap(&heap[1], &heap[leaf]); arr[i] = heap[leaf]; leaf--; int tmp = 1; while ((tmp * 2) <= leaf) { int left = tmp * 2; int right = tmp * 2 + 1; if (right > leaf) right = left; int target; if (heap[left] < heap[right]) target = left; else target = right; if (heap[tmp] > heap[target]) swap(&heap[tmp], &heap[target]); tmp = target; } } delete heap; } ...
|
自從上了演算法課後,課程中學到了更精闢的堆積處理技巧:
- 獨立出「從指定節點調整堆積」的函數
- 直接塞入所有資料到堆積,然後從倒數第二層調整堆積至樹根
- 取出資料直接採用覆蓋的方式,而非資料交換
這個做法大幅度降低了資料在堆積中搬移與交換的時間。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| ...
void restore(int node, int *heap, int leaf) { while ((node * 2) <= leaf) { int left = 2 * node; int right = 2 * node + 1; if (right > leaf) right = left; int target; if (heap[left] < heap[right]) target = left; else target = right; if (heap[node] < heap[target]) break; swap(&heap[node], &heap[target]); node = target; } } ...
void heap_sort(int *arr, int len) { int *heap = new int[len + 1]; for (int i = 0; i < len; i++) heap[i + 1] = arr[i]; for (int i = (int)(len / 2); i >= 1; i--) restore(i, heap, len); int index = 0; for (int i = len; i >= 1; i--) { arr[index++] = heap[1]; heap[1] = heap[i]; restore(1, heap, i); } delete heap; } ...
|
Stooge Sort
中文為「臭皮匠排序」
《算法導論》思考題中的低效排序算法,
雖然算法本身不實用,但是很好的練習題材。
概念很簡單,從最大的序列開始,如果第一個跟最後一個順序不對則交換,
如果序列大於三,則依序對「前2/3個元素」、「後2/3個元素」、「前2/3個元素」,
重複使用臭皮匠排序,最後就會排完。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| ...
void stooge_sort(int *arr, int len) { if (arr[0] > arr[len - 1]) swap(&arr[0], &arr[len - 1]); if (len >= 3) { int tmp = (int)(len / 3); stooge_sort(arr, len - tmp); stooge_sort(arr + tmp, len - tmp); stooge_sort(arr, len - tmp); } } ...
|
Sleep Sort
中文為「睡眠排序」
充滿魔性的排序方法,根據數值的大小設定延遲進入陣列的時間。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| ... #include <thread> ...
void wait(int value, int *arr, int *index) { this_thread::sleep_for(chrono::milliseconds(value)); arr[*index] = value; (*index)++; }
void sleep_sort(int *arr, int len) { thread *tasks = new thread[len]; int index = 0; for (int i = 0; i < len; i++) tasks[i] = thread(wait, arr[i], arr, &index); for (int i = 0; i < len; i++) tasks[i].join(); delete tasks; } ...
|
Bogo Sort
中文為「猴子排序」
簡單的說,就是隨機洗牌,然後檢查是否排好的排序算法。
雖然不實用,但是具有特別的教育意義。
實作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| ... void bogo_sort(int *arr, int len) { srand(time_t(NULL)); bool sorted = false; while (sorted == false) { sorted = true; for (int i = 0; i < len; i++) swap(&arr[i], &arr[rand() % len]); for (int i = 1; i < len; i++) if (arr[i] < arr[i - 1]) sorted = false; } } ...
|
綜合評估
中文名稱 | 英文名稱 | 最糟複雜度 | 最優複雜度 | 簡介 |
---|
氣泡排序 | Bubble Sort | $O(n^{2})$ | $O(n)$ | 依序選擇相鄰的元素比較、交換的排序方法 |
選擇排序 | Selection Sort | $O(n^{2})$ | $O(n)$ | 重複在未排序的區間選擇最小的放到正確的位置 |
插入排序 | Insertion Sort | $O(n^{2})$ | $O(n)$ | 移動其他元素,並在找到插入點時插入正確的元素 |
雞尾酒排序 | Cocktail Sort | $O(n^{2})$ | $O(n)$ | 左右來回的氣泡排序 |
梳排序 | Comb Sort | $O(n^{2})$ | $O(nlg(n))$ | 間距上的元素順序不符則交換,間距逐次遞減 |
地精排序 | Gnome Sort | $O(n^{2})$ | $O(n)$ | 到未排序的區間透過相鄰交換,將元素換到正確的位置上 |
奇偶排序 | Odd-even Sort | $O(n^{2})$ | $O(n)$ *平行 | 分奇數位置、偶數位置,分別做氣泡排序 |
希爾排序 | Shell Sort | $O(n^{2})$ | $O(nlg(n))$ | 對固定間距的元素做插入排序,間距逐次遞減 |
桶子排序 | Bucket Sort | $O(n^{2})$ | - | 將元素分群,對不同群做好排序再合併 |
計數排序 | Counting Sort | $O(n+k)$ | - | 紀錄每種元素的出現次數,利用出現次數重新排列數字 |
基數排序 | Radix Sort | $O(wn)$ | - | 依序對每一位做排序,位數逐次遞增(或遞減) |
合併排序 | Merge Sort | $O(nlg(n))$ | $O(n)$ | 將元素分成兩半,直至無法分開後,依照順序合併 |
快速排序 | Quick Sort | $O(n^{2})$ | $O(nlg(n))$ | 選擇參考元素,將其他元素與其比較並放到其中一邊 |
二元搜尋樹 | Binary Search Tree | $O(n^{2})$ | $O(nlg(n))$ | 利用資料建立一顆二元搜尋樹後透過中序走訪取得元素 |
堆積排序 | Heap Sort | $O(nlg(n))$ | $O(nlg(n))$ | 利用資料建立堆積,依序取出堆積的樹根,再調整堆積 |
臭皮匠排序 | Stooge Sort | $O(n^{lg(3)/lg(1.5)})$ | $O(n^{lg(3)/lg(1.5)})$ | 起始結束位置不對則交換,遞迴調用前、後、前2/3個元素 |
睡眠排序 | Sleep Sort | $O(max(n))$ | $O(max(n))$ | 利用數值本身的大小讓系統等待,結束等待同時取回元素 |
猴子排序 | Bogo Sort | $O(\infty)$ | $O(n)$ | 亂數洗牌,直到順序正確為止 |
排序動畫演示
效能評估演示
參考資料
參考資料沒有先後關係。