資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學資料結構中排序方法的比較
在這裡，我們將瞭解一些排序方法。排序技術有200多種。我們將瞭解其中的一些。一些排序技術是基於比較的排序，一些是非基於比較的排序技術。
基於比較的排序技術包括氣泡排序、選擇排序、插入排序、歸併排序、快速排序、堆排序等。這些技術被認為是基於比較的排序，因為在這些技術中，值會被比較，並在不同的階段放置到排序位置。在這裡，我們將瞭解這些技術的複雜度。
| 分析型別 | 氣泡排序 | 選擇排序 | 插入排序 | 歸併排序 | 快速排序 | 堆排序 |
|---|---|---|---|---|---|---|
| 最佳情況 | O(n2) | O(n2) | O(n) | O(log n) | O(log n) | O(logn) |
| 平均情況 | O(n2) | O(n2) | O(n2) | O(log n) | O(log n) | O(log n) |
| 最壞情況 | O(n2) | O(n2) | O(n2) | O(log n) | O(n2) | O(log n) |
一些排序演算法是非基於比較的演算法。其中一些是基數排序、桶排序、計數排序。這些是非基於比較的排序，因為在排序時不會比較兩個元素。這些技術的實現方式略有不同。現在我們將根據不同型別的分析來了解它們之間的區別。
| 分析型別 | 基數排序（k是最大位數） | 計數排序（k是計數陣列的大小） | 桶排序（k是桶的數量） |
|---|---|---|---|
| 最佳情況 | O(nk) | O(n + k) | O(n + k) |
| 平均情況 | O(nk) | O(n + k) | O(n + k) |
| 最壞情況 | O(nk) | O(n + k) | O(n2) |
排序技術也可以使用其他一些引數進行比較。一些排序演算法是原地排序演算法，一些是非原地排序演算法。那些不需要任何額外空間的演算法稱為原地排序演算法。例如，快速排序和堆排序是原地排序演算法。但歸併排序是非原地排序技術。
一些演算法是線上演算法，一些是離線演算法。如果演算法在排序過程中接受新元素，則稱為線上排序演算法。在上面提到的技術中，插入排序是線上排序技術。
更新於: 2019年8月27日
6K+ 瀏覽量
廣告