首页 > 试题广场 >

关于快速排序，下列说法正确的有（）

[不定项选择题]
关于快速排序，下列说法正确的有（） 
  • 快速排序是基于比较的排序
  • 快速排序使用了分治的思想
  • 在某些特殊数据中，快速排序的时间复杂度可以达到O(n)
  • 快速排序只能使用递归方式实现
查看答案及解析
添加回答
游子吟头像 游子吟
  “挖坑填数+分治法”，首先令i =L; j = R; 将a[i]挖出形成第一个坑，称a[i]为基准数。然后j--由后向前找比基准数小的数，找到后挖出此数填入前一个坑a[i]中，再i++由前向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中，这样i之前的数都比基准数小，i之后的数都比基准数大。因此将数组分成二部分再分别重复上述步骤就完成了排序。

快排最好的情况是，每次正好中分，复杂度为O(nlogn)。最差情况，复杂度为O(n^2)，退化成冒泡排序


发表于 2019-03-17 17:04:11 回复(3)
你永远得不到的祖奶奶头像 你永远得不到的祖奶奶
快速排序使用了分治的思想，我现在才知道。
发表于 2020-05-28 20:42:03 回复(0)
WOW你懂我意思吧头像 WOW你懂我意思吧

快排还可以用非递归的方法

发表于 2020-02-13 22:18:04 回复(0)
Philgent-3头像 Philgent-3
分治和动态规划里面的概念相同吧
发表于 2022-11-04 01:05:40 回复(0)
不做人了头像 不做人了
比较的意思要和数组中其他元素比较
计数排序 桶排序不需要 比较
编辑于 2020-04-28 18:54:24 回复(0)
提交观点

问题信息

C++工程师 系统工程师 安卓工程师 小米集团 运维工程师 前端工程师 算法工程师 测试工程师 2019 排序 Java工程师
来自：小米2019秋招系统软...
上传者：小小
难度：
5条回答 5960浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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