各种内排序算法性能比较(个人总结)
稳定性 | 最好情况 | 最坏情况 | 平均 | 空间复杂度 | 确定最终位置 | |
---|---|---|---|---|---|---|
简单选择排序(属于选择排序) | 不稳定 | O(n²) n-1趟 | O(n²) n-1趟 | O(n²) n-1趟 | O(1) | 一趟排序后能确定某个元素的最终位置 |
直接插入排序 | 稳定 | O(n) n-1趟 | O(n²) n-1趟(反向有序) | O(n²) n-1趟 | O(1) | 一趟排序后不能确定某个元素的最终位置 |
冒泡排序(属于交换排序) | 稳定 | O(n) 1趟 | O(n²) n-1趟 | O(n²) n/2趟 | O(1) | 一趟排序后能确定某个元素的最终位置 |
快速排序(属于交换排序) | 不稳定 | O(nlog2底n) | O(n²) n-1趟(正向/反向有序) | O(nlog2底n) | O(log2底n)~O(n) | 一趟排序后能确定某个元素的最终位置 |
两路合并排序 | 稳定 | O(nlog2底n)log2底n向上取整 趟 | O(nlog2底n) log2底n向上取整 趟 | O(nlog2底n) log2底n向上取整 趟 | O(n) | 一趟排序后不能确定某个元素的最终位置 |
堆排序(属于选择排序) | 不稳定 | O(nlog2底n) n-1 趟 | O(nlog2底n) n-1趟 | O(nlog2底n) n-1趟 | O(1) | 一趟排序后能确定某个元素的最终位置 |
版权声明:本文为博主原创文章,如有错误,恳请大家在评论区指出,在下不胜感激~如要转载注明出处即可~