選擇排序法
插入排序法
冒泡排序法
歸并排序法
- 自頂向下
- 自底向上
快速排序法
- 單路快速排序法
- 雙路快速排序法
- 三路快速排序法
堆排序法
希爾排序法
- 不同的步長(zhǎng)序列
| 方法 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 特殊數(shù)據(jù) | 其他 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 選擇排序法 | O(n^2) | O(1) | 不穩(wěn)定 | ||
| 插入排序法 | O(n^2) | O(1) | 完全有序數(shù)組，時(shí)間O(n) | 穩(wěn)定的(依賴(lài)具體實(shí)現(xiàn)) | |
| 冒泡排序法 | O(n^2) | O(1) | 完全有序數(shù)組，時(shí)間O(n) | 穩(wěn)定的(依賴(lài)具體實(shí)現(xiàn)) | |
| 歸并排序法 | O(nlogn) | O(n) | 完全有序數(shù)組森篷，優(yōu)化之后時(shí)間O(n) | O(nlogn)求數(shù)組中的逆序?qū)€(gè)數(shù) | 穩(wěn)定的(merge過(guò)程中相同元素沒(méi)機(jī)會(huì)跳到前面去) |
| 快速排序法 | O(nlogn) * (存在隨機(jī)期望復(fù)雜度) | O(1) | 含有相同元素?cái)?shù)組痰驱，三路快排時(shí)間O(n) | O(n)求解selectK, topK | 不穩(wěn)定的(隨機(jī)標(biāo)定點(diǎn)直接打亂了順序) |
| 堆排序法 | O(nlogn) | O(1) (優(yōu)化heapify之后) | 堆夺荒；優(yōu)先隊(duì)列 O(nlogk)解決selectK, topK問(wèn)題 | 不穩(wěn)定的 | |
| 希爾排序法 | O(nlogn)-O(n^2) | O(1) | 分組的思想 | 不穩(wěn)定(分組數(shù)據(jù)之間有間隔) |
排序算法的穩(wěn)定性
- 排序前相等的倆個(gè)元素，排序后相對(duì)位置不變。一個(gè)穩(wěn)定的排序算法也有可能被實(shí)現(xiàn)成不穩(wěn)定的。
-
如果元素只有一個(gè)域叮姑，穩(wěn)定性沒(méi)有意義。
穩(wěn)定性
域
