排序算法大體可分為兩種：
一種是比較排序，時間復(fù)雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。
另一種是非比較排序，時間復(fù)雜度可以達(dá)到O(n)，主要有：計數(shù)排序，基數(shù)排序等。
| 算法名稱 | 原理 | 發(fā)明時間 | 發(fā)明人 | 平均時間復(fù)雜度 | 最壞時間復(fù)雜度 | 最優(yōu)時間復(fù)雜度 | 空間復(fù)雜度（輔助空間） | 穩(wěn)定性 |
|---|---|---|---|---|---|---|---|---|
| 冒泡排序(Bubble Sort) | 重復(fù)地遍歷要排序的序列，一次比較兩個元素，如果它們順序錯誤就把它們交換過來。 | O(n^2) | O(n^2) | O(n) | O(1) | 穩(wěn)定 | ||
| 選擇排序(Selection Sort) | 在未排序序列中找到最?。ù螅┰?，存放到已排序序列的末尾。 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 | ||
| 插入排序(Insertion Sort) | 對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。 | O(n^2) | O(n^2) | O(n) | O(1) | 穩(wěn)定 | ||
| 希爾排序(Shell Sort) | 將待比較的所有元素分為幾個區(qū)域，讓一個元素可以一次性地朝最終位置前進(jìn)一大步。 | 1959 | Donald Shell | 根據(jù)步長序列的不同而不同 | 根據(jù)步長序列的不同而不同。已知最好的： O(n(logn)^2) | O(n) | O(1) | 不穩(wěn)定 |
| 歸并排序(Merge Sort) | 將兩個已經(jīng)排序的序列合并成一個序列。 | 1945 | 馮·諾伊曼 | O(nlogn) | O(nlogn) | O(n) | O(n) | 穩(wěn)定 |
| 快速排序(Quick Sort) | 使用分治策略把一個序列分為兩個子序列，其中一個子序列所有元素的鍵值都比基準(zhǔn)小，另一個都比基準(zhǔn)大。 | 1962 | 托尼·霍爾（Tony Hoare） | O(nlogn) | O(n^2) | O(nlogn) | 根據(jù)實(shí)現(xiàn)方式不同而不同 | 不穩(wěn)定 |
| 堆排序(Heap Sort) | 堆是一棵完全二叉樹，其子節(jié)點(diǎn)的鍵值總是小于（或大于）它的父節(jié)點(diǎn)。 | 1964 | 羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams） | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 基數(shù)排序(Radix Sort) | 將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)進(jìn)行比較。 | 1887 | 赫爾曼·何樂禮（Herman Hollerith） | O(kn) | O(n+k) | 穩(wěn)定 | ||
| 計數(shù)排序(Counting Sort) | 把鍵值作為計數(shù)數(shù)組的索引。 | 1954 | Harold H. Seward | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 穩(wěn)定 |
