come and bite me 2023-03-05 01:44 采纳率: 100%
浏览 101
已结题

关于快速排序算法的问题

我看的是Princeton 的Algorithms 4th,在快速排序这一章,partition部分的比较数到底是N-1还是N还是N+1啊?有人教教我怎么算吗?
或者有人帮忙证明一下快速排序的比较数为什么约等于2NlnN?

  • 写回答

10条回答 默认 最新

  • 「已注销」 2023-03-05 13:16
    关注

    “Devil组”引证GPT后的撰写:

    • 快速排序的比较次数取决于分割(partition)步骤中基准元素的选择方法和分割时元素的排列情况。在最坏情况下,分割过程将分割数组为两个不均衡的部分,并且每次分割只会将一个元素移动到其最终的位置,因此比较次数将达到N-1。在最好的情况下,每次分割都能将数组均分成两部分,比较次数为NlogN。平均情况下,我们可以预期比较次数约为2NlnN。

    下面是快速排序平均比较次数约为2NlnN的证明概述:

    • 对于快速排序的平均比较次数进行分析,我们需要考虑随机地选择基准元素的影响。我们可以考虑一个假想的排序过程,其中我们将基准元素选择为随机的,每个元素被选中的概率相等。在这种情况下,我们期望在进行分割操作时,选中的基准元素将数组分成两个大小大致相等的部分。
    • 现在假设我们有一个大小为N的数组,我们要对其进行排序。为了方便,我们将N假定为2的幂,因此有N = 2^k。在第一轮分割之后,数组将被分成两个大小大致相等的子数组,每个大小为N/2。然后,我们需要对两个大小为N/2的子数组进行排序。
    • 对于子数组的排序,我们仍然采用随机选择基准元素的方法。由于基准元素的选择是随机的,因此我们期望将每个子数组分成大小相等的两个子数组。在这种情况下,我们需要进行2次比较,以将基准元素与子数组的剩余元素进行比较。然后,我们需要对四个大小为N/4的子数组进行排序,每个子数组需要进行2次比较。以此类推,直到我们对大小为1的子数组进行排序。

    因此,快速排序的比较次数可以表示为:

    C(N) = 2NlogN + 2N + 2N + ... + 2 = 2NlnN + O(N)
    
    
    
    • 其中,第一个项表示在主数组中进行的比较数,第二个项表示在子数组中进行的比较数,最后一项是一个小的修正项。因此,我们可以预期快速排序的比较次数约为2NlnN。这个证明仅仅是对快速排序的平均情况进行了分析,最坏情况下的比较次数可能达到N^2
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(9条)

报告相同问题?

问题事件

  • 系统已结题 3月15日
  • 已采纳回答 3月7日
  • 创建了问题 3月5日

悬赏问题

  • ¥50 深度学习运行代码直接中断
  • ¥15 关于#单片机#的问题,请各位专家解答!
  • ¥15 关于#单片机#的问题,请各位专家解答!
  • ¥20 需要完整的共散射点成像代码
  • ¥15 编写vba代码实现数据录入工作
  • ¥15 做过TCL海信电视小米电视相关影视会员软件私我
  • ¥15 Mapreduce是正常的,在运行其他jar包时并没有任何问题,只是在做LogCount.jar 时出的问题。如图所示
  • ¥15 ImportError: DLL load failed while importing _iterative: 找不到指定的模块。
  • ¥15 如何通过交互分析得出某高危患者对放疗获益更多
  • ¥15 相关性分析中,p<0.05, r=0.29,怎么评价相关性呢