排序简答题总结

￡神魔★判官ぃ 2022-05-26 23:05 291阅读 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 条评论，291人围观）

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

相关阅读

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

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

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

相关经济学原理简答题

1. 什么是财富？财富的五种资本形态是什么？答：财富，在狭义上就是等于金钱，而在广义上，财富等于丰富（人生幸福的一切要素）是超越金钱至上的富足的生活。财富有五种形态

偏执的太偏执、/ 2024年03月26日 13:52/ 0 赞/ 89 阅读

相关经济法(简答题)

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

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

相关操作系统简答题

操作系统简答题操作系统概述用户界面进程与进程通信进程互斥、同步与死锁

ゝ一纸荒年。/ 2023年05月31日 03:09/ 0 赞/ 19 阅读

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

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

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

相关计算机网络简答题

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

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

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

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

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

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

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

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

相关排序简答题总结

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

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

相关 Android简答题

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

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