排序简答题总结

￡神魔★判官ぃ 2022-05-26 23:05 186阅读 0赞

**常见的排序算法有哪些？其中哪些是稳定的，哪些是不稳定的？**

**答：**冒泡排序、选择排序、直接插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序、计数排序。

其中，稳定的排序算法有：冒泡排序、直接插入排序、归并排序、基数排序、计数排序。

不稳定的排序算法有：选择排序、希尔排序、快速排序、堆排序。

**排序算法的空间复杂度比较。**

**答：**O(1)：冒泡排序、选择排序、直接插入排序、希尔排序、堆排序。

O(logN)~O(N)：快速排序

O(N)：归并排序

**排序算法的时间复杂度比较。**

**答：**冒泡排序、直接插入排序的时间复杂度为O(n^2)。

快速排序的平均时间复杂度为O(nlogn)，最好为O(nlogn)，最坏达到了O(n^2)。

堆排序的时间复杂度为O(nlogn)，最坏、最好都是O(nlogn)。

归并排序的时间复杂度为O(nlogn)，最坏、最好都是O(nlogn)。

![70][]

答案：D

【解析】冒泡排序的时间复杂度为O(n^2)，最好为O(n)，最坏为O(n^2)。

直接插入排序的时间复杂度为O(n^2)，最好为O(n)，最坏为O(n^2)。

选择排序的时间复杂度为O(n^2)，最好为O(n^2)，最坏为O(n^2)。

快速排序的时间复杂度为O(nlogn)，最好为O(nlogn)，最坏为O(n^2)。

1. **常见的排序算法有哪些？**

**答：**冒泡排序、选择排序、直接插入排序、归并排序、快速排序、希尔排序、堆排序、基数排序、计数排序。

**2.时间复杂度为O(N^2)的排序算法有哪些？**

**答：**冒泡排序、选择排序、直接插入排序。

** **

**3.时间复杂度为0(N\*logN)的排序算法有哪些？**

**答：**归并排序、快速排序、希尔排序、堆排序。

**4.时间复杂度为O(N)的排序算法有哪些？**

**答：**基数排序、计数排序。

**5.经典排序算法的空间复杂度**

答：O(1)插入排序、选择排序、冒泡排序、堆排序、希尔排序

O(logN)~O(N)快速排序

O(N)归并排序

O(M)计数排序、基数排序

**6.算法中稳定性的概念？**

**答：**假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。

**7.稳定的排序算法有哪些？**

**答：**冒泡排序、直接插入排序、归并排序、计数排序、基数排序。

**8.不稳定的排序算法有哪些？**

**答：**选择排序、快速排序、希尔排序、堆排序等。

**补充说明一：排序算法无绝对优劣**

通常不能随便说哪种排序算法好。这个和要排序的元素相关。例如对人的年龄排序或者身高排序，因为这种数据范围通常比较小，可以考虑采用计数排序。但是对于均匀分布的整数，计数排序就不合适了。除非面试题特别说明，否则认为要排序的数据范围是均匀分布的。

**补充说明二：为什么叫快速排序**

快速排序之所以叫快速排序，并不代表它比堆排序和归并排序优良。在最好情况下，它的渐进复杂度与堆排序和归并排序是相同的。只是快速排序的常量系数比较小而已。

[70]: /images/20220527/428490a1be7a48d9816ecb5b7d8d68b0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java最新简答题

1.get与post请求区别？区别1: get重点在从服务器上获取资源，post重点在向服务器发送数据；区别2： get传输数据是通过URL请求，以field（

素颜马尾好姑娘i/ 2024年04月06日 11:16/ 0 赞/ 16 阅读

相关化学工艺学简答题

1. 简述化学工程学和化学工艺学的研究范畴？化学工程学是研究化学工业和其他过程工业生产中所进行的化学过程和物理过程k共同规律的一门科学，其重要任务是研究有关工程因素对过程和

╰半橙微兮°/ 2024年04月03日 09:39/ 0 赞/ 14 阅读

相关数据库原理简答题总结

数据库原理简答题总结　第一章数据库概论 1.人工管理阶段数据管理的特点：（1）数据不保存在机器中（2）无专用的软件对数据进行管理（3）只有程

ゞ浴缸里的玫瑰/ 2024年03月27日 19:21/ 0 赞/ 26 阅读

相关经济法(简答题)

经济法简答题 1、简述我国经济法的调整对象？p8 答：我国经济法调整对象包括：①国家经济管理关系。经济管理关系即纵向经济关系。这里主要指国家通过国家机关及其授权组织对企业、

╰+哭是因爲堅強的太久メ/ 2024年03月26日 10:55/ 0 赞/ 22 阅读

相关《微机原理与接口技术》简答题总结

文章目录重点：一、8086/8088 二、半导体存储器三、寻址方式四、汇编五、中断技术六、输入输出 -------

你的名字/ 2023年01月15日 08:06/ 0 赞/ 119 阅读

相关计算机网络简答题

面向连接和非连接的服务特点 1. 面向连接的服务：通信双方在进行通信之前，要事先建立一个完整的可以彼此沟通的通道，在通信过程中整个连接的情况可以被实时的监控和管理 2.

太过爱你忘了你带给我的痛/ 2023年01月01日 03:42/ 0 赞/ 171 阅读

相关电力电子技术简答题总结

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

谁借莪１个温暖的怀抱￠/ 2022年12月25日 11:50/ 0 赞/ 125 阅读

相关 c#简答题题库_.net笔试题一（简答题）

1. 简述 private、 protected、 public、 internal 修饰符的访问权限答： private : 私有成员, 在类的内部才可以访问。 pr

缺乏、安全感/ 2022年10月26日 14:23/ 0 赞/ 114 阅读

相关排序简答题总结

常见的排序算法有哪些？其中哪些是稳定的，哪些是不稳定的？答：冒泡排序、选择排序、直接插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序、计数排序。其中，稳定的排序

￡神魔★判官ぃ/ 2022年05月26日 23:05/ 0 赞/ 187 阅读

相关 Android简答题

-------------------- 第三章： 1.ListView 手动加载实现思路？ 1.为ListView增加一个footView脚视图(ListVie

╰+攻爆jí腚メ/ 2022年03月14日 15:16/ 0 赞/ 201 阅读