先來個表格總結(jié)直觀展示下：

各種內(nèi)部排序算法的性質(zhì)

? ? ? ? ? ?算法種類		? ? ? ? ? ? ? ? ? ?時間復(fù)雜度			?空間復(fù) 雜度	穩(wěn)定性
		最好情況	平均情況	最壞情況
插入排序	直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	穩(wěn)定
	折半插入排序	O(n)	O(n^2)	O(n^2)	O(1)	穩(wěn)定
	希爾排序	O(n^1.3)	O(nlogn)	O(n^2)	O(1)	不穩(wěn)定
交換排序	冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	穩(wěn)定
	快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)	不穩(wěn)定
選擇排序	簡單選擇排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不穩(wěn)定
	堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不穩(wěn)定
歸并排序	二路歸并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	穩(wěn)定
? ? ? ? ? ? ? 基數(shù)排序		O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	穩(wěn)定

?

下面詳細(xì)說明一下：

?1.時間復(fù)雜度：（不包括基數(shù)排序）

平均情況下，快速排序、希爾排序（和增量有關(guān)，n在特定范圍內(nèi)為O(n^1.3)）、歸并排序、堆排序時間復(fù)雜度為O(nlogn)，其他均為O(n^2)；

最壞情況下，快速排序、希爾排序為O(n^2)，其他均和平均情況下相同；

最好情況下，直接插入排序、折半插入排序、冒泡排序時間復(fù)雜度為O(n)（初始序列有序）。

2.空間復(fù)雜度：

快速排序O(logn)，2路歸并排序O(n)，基數(shù)排序O(r)，其他都是O(1)。

3.穩(wěn)定性：

希爾排序、快速排序、簡單選擇排序、堆排序不穩(wěn)定，其他都是穩(wěn)定的。

4.其他：

經(jīng)過一趟排序，能保證一個元素到達(dá)最終位置：交換排序（冒泡排序、快速排序）、選擇排序（簡單選擇排序、堆排序）。

5.例題：

若輸入數(shù)據(jù)存儲在帶頭結(jié)點的雙向循環(huán)鏈表中，下面排序算法是否仍然適用？

• 快速排序：適用。因為可以快速定位到第一個元素和最后一個元素結(jié)點，然后通過1個指針從頭部向后移動，另外一個指針從尾部向前移動，逐一與基準(zhǔn)元素進行比較，并能夠通過修改指針完成結(jié)點交換操作。
• 直接插入排序：適用。因為可以方便地找到前驅(qū)后繼和通過修改指針完成結(jié)點交換操作。
• 簡單選擇排序：適用。因為只需要移動指針遍歷鏈表并通過修改指針完成結(jié)點交換。
• 堆排序：不適用。因為雙向循環(huán)鏈表無法很方便地找到完全二叉樹的雙親與孩子結(jié)點。

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的超详细！各种内部排序算法的比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。