排序算法 | 稳定性 | 最优时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
---|---|---|---|---|---|
选择排序 | 不稳定 | \(O(N^2)\) | \(O(N^2)\) | \(O(N^2)\) | \(O(1)\) |
冒泡排序 | 稳定 | \(O(N)\) | \(O(N^2)\) | \(O(N^2)\) | \(O(1)\) |
插入排序 | 稳定 | \(O(N)\) | \(O(N^2)\) | \(O(N^2)\) | \(O(1)\) |
计数排序 | 稳定 | \(O(N+W)\) | \(O(N+W)\) | \(O(N+W)\) | \(O(W)\) |
基数排序(使用计数排序为内层排序) | 稳定(取决于内层排序) | \(O(kN+\sum_{i=1}^{k}w_i)\) | \(O(kN+\sum_{i=1}^{k}w_i)\) | \(O(kN+\sum_{i=1}^{k}w_i)\) | \(O(k+N)\) |
快速排序 | 不稳定 | \(O(NlogN)\) | \(O(NlogN)\) | \(O(N^2)\) | \(O(1)\) |
归并排序 | 稳定 | \(\Theta(NlogN)\) | \(\Theta(NlogN)\) | \(\Theta(NlogN)\) | \(O(N) / O(1)\) |
堆排序 | 不稳定 | \(O(NlogN)\) | \(O(NlogN)\) | \(O(NlogN)\) | \(O(1)\) |
桶排序(使用插入排序为内层排序) | 稳定(取决于内层排序) | \(O(N)\) | \(O(N+N^2/k+k)\) | \(O(N^2)\) | \(O(k)\) |
希尔排序 | 不稳定 | \(O(N)\) | \(O(NlogN)\) | \(o(N^2)\) | \(O(1)\) |
锦标赛排序 | 不稳定 | \(O(NlogN)\) | \(O(NlogN)\) | \(O(NlogN)\) | \(O(N)\) |
tim排序 | 稳定 | \(O(N)\) | \(O(NlogN)\) | \(O(NlogN)\) | \(O(N)\) |