各种内排序算法性能比较(个人总结)

稳定性 最好情况 最坏情况 平均 空间复杂度 确定最终位置
简单选择排序(属于选择排序) 不稳定 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) 一趟排序后能确定某个元素的最终位置

版权声明:本文为博主原创文章,如有错误,恳请大家在评论区指出,在下不胜感激~如要转载注明出处即可~