首页 > 试题广场 >

快速排序的思想是递归的，但是它的平均效率却是众多排序算法中最

[问答题]
快速排序的思想是递归的，但是它的平均效率却是众多排序算法中最快的，为什么？请结合本例说明你对递归程序的理解。
添加回答
如果大雄没有机器猫头像 如果大雄没有机器猫
拙见：
就拿归并排序来说吧，归并的思想是对每段进行排序，排好序之后，合并，再对合并段排序。虽然每次都进行了排序，但是没有一个元素在一次排序中落在最终位置上。归并的操作最小单元是段。但是对于快速排序来说，它的操作最小单元是小于归并的，最小单元是每个一元素，快排的每一次操作都会将一个元素落实于其最终位置，因此我觉得快排快是因为两点：一：每趟排序都会将一个元素落实于其最终位置。二：它的操作最小单元是最基本的元素本身，而不是划分出来的段之类的。
============
快速排序的步骤大致：先将元素放置在最终位置，然后划分。重复，直到元素个数为一。
归并是：划分，直到元素个数为一，归并，排序。
真正的差异就在排序和划分的顺序上。
编辑于 2015-06-22 14:25:02 回复(1)
更多回答
把那碗饭给我头像 把那碗饭给我
快速排序快的主要原因是大大减少了比较和交换的次数，因为按基准数切分的两半数组，在一个数组里面的数据是绝对不会和第二个数组里面的数字产生比较的机会的，所以大幅度降低了做无用功的机会。
发表于 2023-03-18 22:12:00 回复(0)
zatrix头像 zatrix
 首先，快排的核心思想是分治而不是递归，用循环一样可以写快排。之所以他的平均效率会是nlogn，取决于二分。而且快排并不是最快的排序算法，最快的排序算法是基数排序。归并排序在确保数据的有序性的同时能保证对所有数据的排序时间都在nlogn，相比平均时间而言，归并排序的时间复杂度应该更稳定，更低。
其次，如果快排使用递归来实现，那么考虑的因素在于，快排解决问题的方法使得一个排序问题可以分成若干子排序问题。而子排序问题的解决方法与父问题相同。这样就可以用同一个函数来进行处理。即递归程序可以对于反复求解同一问题的问题进行简化代码编写。
发表于 2015-06-23 10:28:07 回复(0)
SunburstRun头像 SunburstRun
从这里可以看出来，递归不一定不适合写程序，用在恰当的地方也有很大用处
用递归能解决的问题通常能将问题不断缩小为性质相同但规模更小的问题，直到问题足够小能够直接解决，而且递归程序看起来非常简洁，是一种非常好的手段，但一般情况下会产出很多无用的东西，衡量好再用递归
编辑于 2015-06-22 23:42:42 回复(0)
newcomer头像 newcomer
快速排序的基本思想是递归的，这也就意味着每次排序都能将数据的规模减半(分而治之);
而每次比较都是前半部分(子集)、后半部分(子集)与选取的主元进行比较，使其各归其位，逐次递归，这些元素都不会再参与比较，已经位于最终的位置上。

发表于 2015-06-22 14:08:38 回复(0)
提交观点

问题信息

盛趣游戏 排序 递归
上传者：DEATH
难度：
5条回答 28207浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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