首页 > 试题广场 >

在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而

[单选题]

在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（）。

查看答案及解析

LydiaYuan

快排最差： (n+1)*n/2-1

冒泡最差：n^2/2-n/2

http://www.cs.toronto.edu/~guerzhoy/180/lectures/W10/lec3/BubbleSortCompl.html

发表于 2019-06-29 10:17:30 回复(0)

宠你＆我的天性

快排在无序时是最快的内部排序算法

发表于 2018-12-05 14:32:40 回复(0)

小赵想找个好工作

快速排序是把数列按一个枢纽值分成两部分分别排序，所以效率高。但是若原数据为有序，并且选择的枢纽值为第一个数时，那在分块时会将一个第一个数前面的数（也就是没有）分为一块，将除第一个数的所有数分成了另一块。这样一来，每一次分块都只减少了一个值，而每次分块的时间为O（N），所以总时间为O（N^2）。

发表于 2020-08-01 20:07:56 回复(0)

YangFong

为什么会是快排呢？

我当时想的情况是：样本随机选择不就好了，情况不至于太糟糕。

但正因为是随机（不稳定），更需要考虑最糟情况（每次都是数组中最大或最小元素）。

所以此处快排的样本选择，需要默认为数组的第一个元素。于是乎，时间复杂度就会很高了。

发表于 2023-02-04 21:30:26 回复(0)

你的offer对我打了烊

此种情况下快排基本退化成冒泡

发表于 2020-05-02 22:43:11 回复(0)

听雨眠醉蝉声

快排还需要分块排序，浪费时间

发表于 2017-08-04 10:02:40 回复(0)

提交观点

问题信息

排序

上传者：呼呼L

难度：

6条回答 177收藏 7864浏览

扫一扫，把题目装进口袋