Closed. This question is opinion-based。它当前不接受答案。












想改善这个问题吗?更新问题,以便editing this post用事实和引用来回答。

3年前关闭。



Improve this question






我认为合并排序是分而治之,因为,

除法-数组按字面意义划分为子数组,无需任何处理(比较/交换),问题大小减半/四分之一/...。

征服-通过处理(cc / swap)merge()那些子数组

代码给人的印象是分而治之,

if(hi <= lo) return;
int mid = lo + (hi-lo)/2; //No (compare/swap) on elements before divide
sort(a, aux, lo, mid); // Problem is halved(Divide)
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid); // (Compare/swap) happens here during Merge - Conquer



合并排序跟踪说,该问题被细化然后处理,

sorting - 快速分类是一种分而治之的方法吗?-LMLPHP


但是在快速排序中

首先,使用分区元素(枢轴)处理(比较/交换)完整数组并固定枢轴的最终位置,然后将问题大小减半/四分之一/ ..以进行重新分区,

代码不会给人以分而治之的印象,

if(hi <= lo) return;
int j = partition(a, lo, hi); // Do you call this divide phase?
sort(a, lo, j-1);  // This looks like divide phase, because problem is halved
sort(a, j+1, hi);



快速排序跟踪,显示处理从完整的阵列开始,然后达到粒度级别,

sorting - 快速分类是一种分而治之的方法吗?-LMLPHP

问题:


我对Divide Phase的理解意味着减少(一半)问题的大小。在快速排序中,您是否考虑使用数据透视处理(比较/交换)数组和分区作为除法阶段?
我对征服阶段的理解意味着收集/合并。简而言之,征服阶段在哪里意味着什么?




            Note: Am a beginner, in sorting algorithms

最佳答案

分而治之算法分为三个阶段:


划分,
征服,
结合,


对于合并排序(http://www.cs.umd.edu/~meesh/351/mount/lectures/lect6-divide-conquer-mergesort.pdf):


分割:将阵列分成2个子阵列,
征服:以递归方式合并排序结果子数组,
合并:将两个已排序的子数组合并到一个已排序的列表中。


快速排序(https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf):


分割:首先重新排列,然后将阵列分成2个子阵列,
征服:快速递归地对结果子数组进行排序,
合并:无。


注意:感谢罗切斯特大学和马里兰大学CS系。

10-07 18:56
查看更多