算法 | 是否穩(wěn)定 | 是否為原地排序 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
---|---|---|---|---|
冒泡排序 | 是 | 是 | N*N | 1 |
選擇排序 | 否 | 是 | N*N | 1 |
插入排序 | 是 | 是 | N*N | 1 |
歸并排序 | 是 | 否 | N*logN | N |
快速排序 | 否 | 是 | N*logN | logN |
堆排序 | 否 | 是 | N*logN | 1 |
希爾排序 | 否 | 是 | N*logN | 1 |
基數(shù)排序 | 是 | 否 | N | M:桶的數(shù)量 |
計(jì)數(shù)排序 | 是 | 否 | N | M:桶的數(shù)量 |
冒泡排序
image
選擇排序
image
運(yùn)行時(shí)間與輸入無關(guān)
數(shù)據(jù)移動(dòng)最少
插入排序
image
對(duì)于部分有序數(shù)組十分高效选浑,適合小規(guī)模數(shù)組
歸并排序
image
merge時(shí),判斷是否有序顿仇,若有序則無需merge操作
快速排序
image
case:
數(shù)組中出現(xiàn)超過一半的數(shù)字淘正;
最小的k個(gè)數(shù);
堆排序
image
希爾排序
image
基數(shù)排序
image
計(jì)數(shù)排序
image