1.ソートの表まとめ
| ソート名 | 最良の時間計算量 | 平均時間計算量 | 最悪時間計算量 | 安定性 |
|---|---|---|---|---|
| バブルソート | O(n^2) | O(n^2) | O(n^2) | 安定 |
| 選択ソート | O(n^2) | O(n^2) | O(n^2) | 不安定 |
| 挿入ソート | O(n^2) | O(n^2) | O(n^2) | 安定 |
| マージソート | O(nlogn) | O(nlogn) | O(nlogn) | 安定 |
| クイックソート | O(nlogn) | O(nlogn) | O(n^2) | 不安定 |
| シェルソート | O(nlogn) | O(nlogn) | O(n^2) | 不安定 |
| ヒープソート | O(nlogn) | O(nlogn) | O(nlogn) | 不安定 |
| 計数ソート | O(n) | O(n+k) | O(n+k) | 安定 |
| 基数ソート | O(n) | O(d(n+k)) | O(d(n+k)) | 安定 |
| パケットソート | O(n) | O(n+n^2/k+k) | O(n^2) | 安定 |