首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 快速排序
题目

下列说法中错误的是：（）

A.插入排序某些情况下复杂度为O（n）

B.排序二叉树元素查找的复杂度可能为O（n）

C.对于有序列表的排序最快的是快速排序

D.在有序列表中通过二分查找的复杂度一定是O（log2n）

上一题 下一题
解答

正确答案是 C

A：数据有序时，插入排序的时间复杂度就是O(n)
B：比如只有右孩子结点的树
C：快排是在无序的情况下排序比较快，所以C说法不正确
D：一定是O(nlog2n)
C 10条回复 评论
子不语

二分查找最差复杂度为O(n)。C是错的，但是D选项对吗？

发表于 2018-10-13 10:50:41
0 0
王王王

CD都错，C假如在最坏的情况下，快排肯定不是最好的
D中二分查找可能是o（n

发表于 2018-10-13 10:50:32
0 0
人生赢家

当原数列基本有序时，直接插入法和冒泡排序的算法复杂度降低为O（n）,而快速排序的复杂度将升高到n的平方级。

发表于 2018-10-13 10:50:17
0 0
咻辉

插入排序伪代码如下：

for i = 1 to n
    key = a[i]
    j      = i - 1;
    while (j>=0 && a[j] >key )
        a[j+1] = a[j] ;//元素后移
        --j
    a[j+1] = key;

当元素有序是，时间复杂度为O(n)

发表于 2018-10-13 10:50:06
0 0
子不语

基本有序的序列用插入排序最快

发表于 2018-10-13 10:49:45
0 0
王王王

快速排序是在数据为无序时才最快。

发表于 2018-10-13 10:49:34
0 0
遇见

对于有序的列表，排序最快的是插入排序，时间复杂度O(N)
对于无序的列表，排序最快的是快速排序，时间复杂度O(Nlog2N)

发表于 2018-10-13 10:49:18
0 0
大葫芦

快排最坏的情况是有序状态O（n^2）,有序列表中通过二分查找的复杂度是 O（logN）

发表于 2018-10-13 10:49:05
0 0
咻辉

有序列表使用快排将达到最坏的情况0（n2）。有序列表最快的是二分查找的复杂度是   O（logN）。
对排序算法进行整理：简单排序时间复杂度都为O（n2），空间复杂度为O（1）,简单排序又包括冒泡（稳定），选择（不稳定），插入（稳定）。但在速度上插入大于选择大于冒泡。
高级排序：希尔排序（基于插入排序），    O（N*(logn)2）,不稳定；快排最好（O（N*logN）)最坏O（n2）--当元素有序时、，空间复杂度为O（logn），不稳定 。
堆排序最好最坏都一样（nlogn）但是需要一个辅助存储point，所以空间复杂度为O(1)，不稳定。
归并排序最好最坏（nlogn），空间复杂为O（n），稳定。
基数排序最好最坏（O(d（n+rd）)），空间复杂为O（rd）不稳定。

发表于 2018-10-13 10:48:51
0 0
大葫芦

对于有序的列表，排序最快的是插入排序，时间复杂度O(N)，底下回答的人都没回答道正点上。

发表于 2018-10-13 10:48:40
0 0
问题信息
分类：数据结构 - 快速排序
难度:
最新校招难题刷题，快来进刷题群吧
相关试题