閱： 4860 | 回： 3
等級:高手
-
積分:117
-
財富值:1.00
-
身份:普通用戶
前言
顧名思義，所謂排序算法（Sorting Algorithm）就是將一組數(shù)據(jù)按某種特定的順序重新排列組織。顯然，這一需要是我們在日常處理工作當(dāng)中總是要用到的。這也是排序算法是計算機(jī)世界中最為重要的算法的原因。最為常見的順序是 數(shù)值順序 和 字符順序。對于一些其它算法的優(yōu)化，一個高效的排序算法是起決定性作用的，比如查找、合并等。
排序算法的分類與評價
顧名思義，所謂排序算法（Sorting Algorithm）就是將一組數(shù)據(jù)按某種特定的順序重新排列組織。顯然，這一需要是我們在日常處理工作當(dāng)中總是要用到的。這也是排序算法是計算機(jī)世界中最為重要的算法的原因。最為常見的順序是 數(shù)值順序 和 字符順序。對于一些其它算法的優(yōu)化，一個高效的排序算法是起決定性作用的，比如查找、合并等。
排序算法的分類與評價
- 計算復(fù)雜度（Computational Complexity），包括最壞、平均、最佳情況，通常由數(shù)據(jù)元素的數(shù)量（n）來計算，而用大O符號來表達(dá)。理想的計算復(fù)雜度是 O(n)，但一般而言，好的性能是 O(n log n)，平均性能是 O(log^2 n)。
- 空間使用（Memory Usage），指除了待排序的源數(shù)據(jù)外，算法所需的額外的臨時存儲空間。通常將不使用或使用有限個（常數(shù)）元素O(1)額外空間的排序算法，稱為原地排序算法（In Place Sorting），比如冒泡排序。
- 穩(wěn)定性（Stability），如果一個排序算法對于源數(shù)據(jù)中兩個排序關(guān)鍵值相同的元素，在排序后不改變其原有順序的，則稱這個排序算法是穩(wěn)定的。比如以下對(2, 9) (1, 3) (2, 7) (3, 4)四個數(shù)字對按第一個數(shù)字排序時，穩(wěn)定的算法則會得到 (1, 3) (2, 9) (2, 7) (3, 4)，而不穩(wěn)定的算法則會得到 (1, 3) (2, 7) (2, 9) (3, 4)。
- 是否使用遞歸，通常程序語言都會對遞歸寄存器有所限制，一些早期的語言甚至不支持遞歸。
- 是否對比，多數(shù)的排序算法都會進(jìn)行元素間的對比，但也有些算法是不用對比的，如計數(shù)排序。
-
排序方式，包括 插入、交換、選擇、合并 等等。
| 排序方式 | 排序算法 |
| 交換排序（Exchange Sort） |
冒泡排序（Bubble Sort） 雞尾酒排序（Cocktail Sort） 快速排序（Quick Sort） 梳排序（Comb Sort） ... |
| 選擇排序（Selection Sort） |
選擇排序（Selection Sort） 堆排序（Heap Sort） ... |
| 插入排序（Insertion Sort） |
插入排序（Insertion Sort） 希爾排序（Shell Sort） 二叉查找樹排序（Binary Tree Sort） ... |
| 合并排序（Merge Sort） |
合并排序（Merge Sort） ... |
| 分配排序（Distribution Sort） |
計數(shù)排序（Counting Sort） 基數(shù)排序（Radix Sort） 桶排序（Bucket Sort） ... |
| 并發(fā)排序（Concurrent Sort） | ... |
| 混合排序（Hybrid Sort） |
內(nèi)省排序（Introsort） ... |
| 其它 |
... |
我的個性簽名
等級:學(xué)者
等級:傳說級人物