将一个从大到小的数组，用以下排序方法排序成从小到大的，（）最_阿里巴巴笔试题

推荐

牛客-007

答案：D

A和B的时间复杂度为N^2

C的平均时间复杂度为NlogN,这里是最坏的情况，也是N^2

编辑于 2015-02-04 14:33:07 回复(7)

菩提旭光

排序方法平均情况最好情况最坏情况辅助空间稳定性

冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定

插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

堆排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(1) 不稳定

归并排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n) 稳定

快速排序 O(n*log(n)) O(n*log(n)) O(n^2) O(1) 不稳定

选择快速堆希尔不稳定排序

编辑于 2015-08-22 16:53:04 回复(3)

不知死活的猫

问题已经明确了，数组反转，就O(n)，这题没啥意思。

发表于 2019-05-19 00:26:54 回复(0)

小田向前冲

我感觉是插入排序，从后往前查不就可以了。

发表于 2016-08-16 14:38:24 回复(0)

奕之为

排序方法平均情况最好情况最坏情况辅助空间稳定性

冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定

插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

堆排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(1) 不稳定

归并排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n) 稳定

快速排序 O(n*log(n)) O(n*log(n)) O(n^2) O(1) 不稳定

发表于 2015-08-21 21:01:24 回复(0)

7_year

这种情况不是插入排序最快吗？堆达不到O（n）

发表于 2015-08-14 15:09:00 回复(5)

牛仔very的忙

插入和冒泡的复杂度都是 O(n^2). ，快速排序在这种情况下是最坏的，时间复杂度是 O(n^2).

堆排序时间复杂度为 O(nlogn)

发表于 2015-08-12 10:49:01 回复(0)

Un-Infinite

排序方法平均情况最好情况最坏情况辅助空间稳定性

冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定

插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

堆排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(1) 不稳定

归并排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n) 稳定

快速排序 O(n*log(n)) O(n*log(n)) O(n^2) O(1) 不稳定

冒泡排序经过优化以后，最好时间复杂度可以达到O(n)。设置一个标志位，如果有一趟比较中没有发生任何交换，可提前结束，因此在正序情况下，时间复杂度为O(n)。选择排序在最坏和最好情况下，都必须在剩余的序列中选择最小（大）的数，与已排好序的序列后一个位置元素做交换，依次最好和最坏时间复杂度均为O(n^2)。插入排序是在把已排好序的序列的后一个元素插入到前面已排好序(需要选择合适的位置)的序列中，在正序情况下时间复杂度为O(n)。堆是完全二叉树，因此树的深度一定是log(n)+1，最好和最坏时间复杂度均为O(n*log(n))。归并排序是将大数组分为两个小数组，依次递归，相当于二叉树，深度为log(n)+1，因此最好和最坏时间复杂度都是O(n*log(n))。快速排序在正序或逆序情况下，每次划分只得到比上一次划分少一个记录的子序列，用递归树画出来，是一棵斜树，此时需要n-1次递归，且第i次划分要经过n-i次关键字比较才能找到第i个记录，因此时间复杂度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2，即O(n^2)。

编辑于 2015-08-19 18:10:16 回复(10)

liuwu265

有人觉得插入排序是O(n)，现在我来分析一下插入排序，假设原来数组为5,4,3,2,1。

第一遍后：4,5,3,2,1。将元素5的位置后移一位然后将元素4插入到前面。

第二遍后：3,4,5,2,1。将前面的4,5都向后面移动一位，再在最前面插入3.

第三遍后：2,3,4,5,1。将2前面的所有元素后移一位，再在最前面插入2.

第四遍后：1,2,3,4,5。将2,3,4,5都向后移动一位，再在最前面插入1.

所以，在这种情况下，插入排序需要移动的次数的最多的，时间复杂度为O(n2)，所以速度不可能是最快的！

发表于 2015-08-22 12:21:36 回复(0)

羽毛

这种排序方式是最坏的情况

发表于 2015-07-19 10:39:32 回复(0)

归途如虹

快速排序，所有关键数据都处于划分数据序列的中间处为最好情况，其时间复杂度 O(n*log(n)) ；数据序列一开始为由小到大或者由大到小的排列方式为最坏情况，其时间复杂度： O(n^2) ，平均时间复杂度： O(n*log(n))。

插入排序和冒泡排序，数据序列一开始就按从小到大的顺序为最好情况，其时间复杂度为： o(n) ；数据序列一开始就按从大到小的顺序为最坏情况下，时间复杂度为 ;o(n.^2)，时间平均复杂度为 o(n.^2) 。

堆排序算法，最好情况下的时间复杂度为：O(n*log(n))，最坏情况下的时间复杂度为; O(n*log(n))，

时间平均复杂度为： O(n*log(n))。选D

发表于 2015-08-19 10:48:43 回复(0)

丕子李

题目说的：”将一个从大到小的数组 “有什么用? 我觉得不考虑空间，用插入排序，每次将后面的值插入在前面已经排好序的第一位，那么只需要o(n)

发表于 2015-08-20 15:33:46 回复(4)

予我深拥

我觉得应该是A，插入排序。时间复杂度为O(N)。排序时，遍历数组，将新元素插在已排序序列的最前端。

发表于 2016-04-01 09:23:10 回复(2)

阿巍十八式

排序方法平均情况最好情况最坏情况辅助空间稳定性

冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定

插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

堆排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(1) 不稳定

归并排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n) 稳定

快速排序 O(n*log(n)) O(n*log(n)) O(n^2) O(1) 不稳定

发表于 2020-10-28 17:21:21 回复(0)

泽思

原：从大到小，要排成：从小到大。

错误看成
原：从大到小，排成：从大到小；然后选了A，插入排序。

发表于 2021-05-26 17:55:46 回复(0)

xiaoli1644

1. 插入排序和冒泡排序复杂度都是n2，注意比较的过程也要算上。 2. 快排的平均复杂度是nlogn，最坏复杂度是n2，我看很多人说逆序就是最坏情况，所以是n2，额谁说逆序就是最坏情况了？快排的复杂度由两部分相乘构成，内层是单次调用时遍历整个数组调整顺序（保证：前 < 参考值 < 后），所以内层复杂度是n，外层是递归的深度，左右子树平衡时递归深度是logn，不平衡时是n，所以内外相乘复杂度最坏就是n2，最好就是nlogn。可以看到影响复杂度的直接因素就是递归深度，本质因素是如何选取参考值使得左右子树是平衡的。因此对于选取指定位置为参考值的策略（如末尾元素），当顺组顺序或者逆序时递归树是极不平衡的单边树，因此才算是最坏情况。而对于更优的选取策略（如选随机位置或者三数取中等），平均复杂度可以确保为nlogn。然而本题还是直接把逆序当成最坏情况n2了，额说这么多还是要理解背后的原理。 3. 堆排序，复杂度nlogn 4. 所以选堆排序

发表于 2020-07-16 09:33:55 回复(0)

dal2020

排序方法平均情况最好情况最坏情况辅助空间稳定性

冒泡排序 O(n^2) O(n) O(n^2)

O(1) 稳定

选择排序 O(n^2) O(n^2) O(n^2)

O(1) 不稳定

插入排序 O(n^2) O(n) O(n^2)

O(1) 稳定

希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2)

O(1) 不稳定

堆排序 O(n*log(n)) O(n*log(n)) O(n*log(n))

O(1) 不稳定

归并排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n)

稳定

快速排序 O(n*log(n)) O(n*log(n)) O(n^2)

O(1) 不稳定

冒泡排序经过优化以后，最好时间复杂度可以达到O(n)。设置一个标志位，如果有一趟比较中没有发生任何交换，可提前结束，因此在正序情况下，时间复杂度为O(n)。选择排序在最坏和最好情况下，都必须在剩余的序列中选择最小（大）的数，与已排好序的序列后一个位置元素做交换，依次最好和最坏时间复杂度均为O(n^2)。插入排序是在把已排好序的序列的后一个元素插入到前面已排好序(需要选择合适的位置)的序列中，在正序情况下时间复杂度为O(n)。堆是完全二叉树，因此树的深度一定是log(n)+1，最好和最坏时间复杂度均为O(n*log(n))。归并排序是将大数组分为两个小数组，依次递归，相当于二叉树，深度为log(n)+1，因此最好和最坏时间复杂度都是O(n*log(n))。快速排序在正序或逆序情况下，每次划分只得到比上一次划分少一个记录的子序列，用递归树画出来，是一棵斜树，此时需要n-1次递归，且第i次划分要经过n-i次关键字比较才能找到第i个记录，因此时间复杂度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2，即O(n^2)。

发表于 2020-04-12 21:43:14 回复(0)