【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
2025考研
计算机考研知识点解析：数据结构之排序算法比较
2022-08-17 10:43:14
计算机考研
考研备考资料
计算机考研是近几年的热门，在考生的备考过程中，数据结构是重要的备考内容之一，今天小编为大家整理了数据结构之排序算法比较的复习内容介绍，能够帮助大家提高备考效率，预祝大家都能顺利进入理想院校。
不同排序算法的时间复杂度和空间复杂度对比
| 方法 | 平均时间 | 最坏时间 | 附加空间 | 稳定性 |
| 直接插入排序 | O(n2） | O(n2） | O（1） | 稳定的 |
| 希尔排序 | - | - | O（1） | 不稳定的 |
| 折半插入排序 | O(n2） | O(n2） | O（1） | 稳定的 |
| 简单选择排序 | O(n2） | O(n2） | O（1） | 不稳定的 |
| 堆排序 | O(nlogn) | O(nlogn) | O（1） | 不稳定的 |
| 冒泡排序 | O(n2） | O(n2） | O（1） | 稳定的 |
| 快速排序 | O(nlogn) | O(n2） | O(logn) | 不稳定的 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定的 |
| 基数排序 | O(d * (n+r)) | O(d * (n+r)) | O(n+r) | 稳定的 |
不同算法对存储结构的要求
希尔排序，折半插入排序，快速排序，堆排序一般需要借助于顺序结构来实现，当采用链式结构时，其算法的时间复杂度会增加。其他算法是顺序结构和链式结构都可以。
不同算法和数据初始状态的关系
1、算法的比较次数和数据的初始状态无关的是：简单选择排序和基数排序
2、算法的趟树和数据的初始状态有关的是：快速排序，其趟数是log2n~n;归并排序的趟树是log2n;
趟数无关的算法是：直接插入排序，折半插入排序，堆，简单选择排序都是n-1趟。基数排序，基数排序的趟树取决于数据的位数，例如三位数就需要3趟，四位数就需要4趟;希尔排序取决于步长的选择;
以上是为大家整理的计算机考研知识点的介绍，希望大家在备考时的努力都能迎来收获，预祝大家能够取得好成绩。
查看全文 
【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
免责声明：本平台部分帖子来源于网络整理，不对事件的真实性负责，具体考研相关内容请以各院校的官网通知为准。如果本站文章侵犯到您的权利，请联系我们（400-108-7500）进行删帖处理。
精选课程
考研资讯
查看更多
考研指导
每日10 份 抢先预约
