首页 > 试题广场 >

下列排序算法中，已基本有序却反而变得更复杂的排序算法是：（

[单选题]

下列排序算法中，已基本有序却反而变得更复杂的排序算法是：（ ）。 

  • 冒泡排序
  • 快速排序
  • 堆排序
  • 简单选择排序
查看答案及解析
添加回答
﹏清心头像 ﹏清心
  1. 快排采用分治的思想，第一次循环结束时，它实际上会产生一个轴，轴左边的都小于轴值，右边的都大于轴值，这样通过轴就分成了两个子序列，再对两个子序列递归快排，最终得到排好序的序列。
  2. 快排对越混乱的数据，排序效果越好，现在说一下为什么对一个基本有序的却更复杂，那是因为这样会导致每次轴划分出的两个子序列，一个趋近于1的数量级，一个趋近于n数量级，那么递归快排就近似总是对n做排序，时间复杂度O（n²），而且非常不符合快排的思想。比较好的情况是每次递归大致平分成两个n/2数量级的子序列，时间复杂度O（nlogn）

发表于 2017-12-26 10:11:55 回复(0)
Wilbur.头像 Wilbur.
快速排序在数组有序的情况下，由于选择了首元素作为中间点，每次快排的时候只分成了大于中间点的序列
发表于 2022-08-20 17:54:49 回复(0)
牛客808362388号头像 牛客808362388号
这个所说的冒泡排序，应该是指的没有优化的冒泡吧。
发表于 2022-01-14 11:20:15 回复(0)
Fcq11头像 Fcq11
感觉对冒泡排序也很有影响啊 比如 逆序 那么每次都需要交换
发表于 2020-04-10 14:23:56 回复(2)
提交观点

问题信息

排序
上传者：zsw3
难度：
4条回答 3050浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号