排序选择题总结

朴灿烈づ我的快乐病毒、 2022-05-13 01:30 184阅读 0赞

# **排序选择题总结** #

![70][]

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

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

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

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

**希尔排序、简单选择排序和快速排序是不是稳定的排序算法？**

**答：**不是。都是不稳定的排序算法。

![70 1][]

答案：C

【解析】反正我知道快速排序对基本有序的数据进行排序，效率特别低。反过来就是答案。

![70 2][]

答案：D E

【解析】稳定的排序算法有：冒泡排序、直接插入排序、归并排序、基数排序、计数排序。

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

![70 3][]

答案：C

【解析】O(1)：冒泡排序、选择排序、直接插入排序、希尔排序、堆排序。

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

O(N)：归并排序

![70 4][]

答案：C

![70 5][]

答案：C

![70 6][]

【解析】选择排序的时间复杂度是O(n^2)。

400^2 对应  400ms

?^2   对应  1600ms

?等于800。

![70 7][]

![70 8][]

![70 9][]

答案：D。

![70 10][]

![70 11][]

【解析】冒泡排序、直接插入排序的时间复杂度为O(n^2)。

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

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

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

![70 12][]

答案：B。

![70 13][]

答案：D。

![70 14][]

![70 15][]

![70 16][]

![70 17][]

答案：4 5 16 18 2 7 20 34 33 29 40

![70 18][]

答案：C

![70 19][]

答案：D

【解析】为什么选D？因为我知道其它三个肯定不对！

![70 20][]

答案：堆排序。构建小顶堆。

![70 21][]

答案：直接插入排序的时间复杂度为O(n^2)，堆排序的时间复杂度为O(nlogn)。

![70 22][]

答案：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)。

![70 23][]

答案：A。

我们可以轻松将B、D排除。看A、C

A排一次后的结果为：9 17 5 21 25 23 30

C排一次后的结果为：5 9 17 21 25 23 30

A再排一次就可以出结果了：5 9 17 21 23 25 30

C再排排一次结果为：5 9 17 21 23 25 30 我们看着也出结果了，但计算机还要进行一轮，对9 17进行排序。

所以选A。

使用快排的话 5 9 17 有序，快排一趟只能确定5的位置，然后还要对9 17 进行一趟快排，但是9 17 5只需进行一趟就能确定三个元素的位置，所以9 17 5 比 5 9 17 更快。

根据快排的原理：A\{21,25,5,17,9,23,30\}选项，先选择21做为最终归位的元素，1、从后向前找小于21的元素，与21交换位置，\{9,25,5,17,21,23,30\}；2、从前向后找大于21的元素\{9,21,5,17,25,23,30\}；3、从后向前找小于21的元素(从原来停止的位置开始)\{9,17,5,21,25,23,30\}4、继续从前向后，结束第一次快排，21归位。得到\{9,17,5,21,25,23,30\}。

![70 24][]

答案：D

[70]: /images/20220513/4af63ead4dca461fa292da5278a1f69f.png
[70 1]: /images/20220513/f6669a32a9ad43f3ba0f7595b69c3cc6.png
[70 2]: /images/20220513/d344e57de9d9410283d0ca127a3e70a9.png
[70 3]: /images/20220513/f0490da824c14933a7bd7cdbbff51ea7.png
[70 4]: /images/20220513/1ab07d1e31384c94bf444f20768b95e3.png
[70 5]: /images/20220513/a97f6b2c828742e9b8ad3a1c03bf051a.png
[70 6]: /images/20220513/7df601259ad341248cf9a1879eae6f3d.png
[70 7]: /images/20220513/1bddff4e57704187854c4fb458a03097.png
[70 8]: /images/20220513/bd02580d224f4a6aa914dd19a801b129.png
[70 9]: /images/20220513/4a58c64260fe4cb081c84423aeda474b.png
[70 10]: /images/20220513/7d1e06c9392a4d3d8b59ff4eb1100c96.png
[70 11]: /images/20220513/4f9748c68c4b4abe9b7b9a618e05790b.png
[70 12]: /images/20220513/c38ea16a49094d818372fabbeb733917.png
[70 13]: /images/20220513/5207e3d13ee0407091bd1dc80f397f6d.png
[70 14]: /images/20220513/0b10ddf660524aff9367052b84a85da5.png
[70 15]: /images/20220513/420bd644dc23499291aa8307558191b4.png
[70 16]: /images/20220513/a45964a077f143c7971954b0fa51ed15.png
[70 17]: /images/20220513/1dd13236ccea4dd6a297fa015d8a459f.png
[70 18]: /images/20220513/8f25e203d32f464694c8d53c1467ec2e.png
[70 19]: /images/20220513/6dc323051bda431cbc03c08952a311aa.png
[70 20]: /images/20220513/46b3776cf88e44409b9335c6ffce45a1.png
[70 21]: /images/20220513/5b9f41ab407e4c3bbd185ccbd86afa4e.png
[70 22]: /images/20220513/54cac41c2fed49e8b426f6dc3a976d61.png
[70 23]: /images/20220513/609048aa4bd84cfb8e9ad0e1e799b4a6.png
[70 24]: /images/20220513/a46b9518865d4fe888a51d7bf27d3ffe.png