简答题

简述归并排序算法和快速排序算法的分治方法。

正确答案

1)归并排序的分治是将数组从中间分开,分别对前后来那个部分进行排序,将排序后的两个数组合并成整个数组的排序。这样分治为递归过程,直到一个元素时返回。
2)快速排序的分治是选取分割元素,以分割元素为界,将数组分成两部分,一部分小于分割元素,一部分大于分割元素,分别对两部分排序。

答案解析

相似试题
  • 在寻找n个元素中第k小元素问题中,如快速排序算法思想,运用分治算法对n个元素进行划分,如何选择划分基准?下面()答案解释最合理。

    单选题查看答案

  • 在寻找n个元素中第k小元素问题中,若使用快速排序算法思想,运用分治算法对n个元素进行划分,应如何选择划分基准?下面()答案解释最合理。

    单选题查看答案

  • 在寻找n个元素中第k小元素问题中,如使用快速排序算法思想,运用分治算法对n个元素进行划分,应如何选择划分基准?下面()答案解释最合理。

    单选题查看答案

  • 请用分治策略设计递归的归并排序算法,并分析其时间复杂性(要求:分别给出divide、conquer、combine这三个阶段所花的时间,并在此基础上列出递归方程,最后用套用公式法求出其解的渐进阶)。

    简答题查看答案

  • 如果修改归并排序算法,将数组分成1/3和2/3大小不等的两部分,分别排序后再归并,算法的最坏时间复杂度有什么变化?

    简答题查看答案

  • 序列4 ,2 ,5 ,3 ,8 ,6 ,7,9,采用归并排序算法(升序),经一趟归并后,序列的结果()。

    填空题查看答案

  • 快速排序算法是基于()的一种排序算法。

    填空题查看答案

  • 在堆排序、快速排序和归并排序中,若只从存储空间考虑,则首先应选取()方法,其次选取快速排序方法。

    填空题查看答案

  • 快速排序、堆排序和归并排序的平均时间复杂度都是(),但其中稳定的排序方法只有()

    填空题查看答案