快速排序是一种分而治之的方法吗？

Question

1. 我认为Merge排序是分而治之的,因为,

   除法 - 数组实际上分为子数组而没有任何处理(比较/交换),问题大小减半/四分之一/ ....

   征服 - merge()这些子阵列处理(比较/交换)

   代码给人的印象是Divide&Conquer,

   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
   

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

2. 但在快速排序中,

   首先,使用分区元素(pivot)处理完成数组(比较/交换)并修复pivot的最终位置,然后将问题大小减半/ Quartered/....进行重新分区,

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

   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);
   

快速排序跟踪,显示处理在完整阵列上启动,然后达到粒度级别,

问题:

1. 我对Divide阶段的理解意味着减少(一半)问题的大小.在快速排序中,您是否考虑使用pivot 处理(比较/交换)数组和分区,如分割阶段？

2. 我对Conquer阶段的理解意味着,收集/合并.快速排序,征服阶段意味着什么？

---

            Note: Am a beginner, in sorting algorithms

Answer 1

Divide&Conquer算法有3个阶段:

1. 划分,
2. 征服,
3. 结合,

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

1. 除以:将数组拆分为2个子数组,
2. 征服:合并对递归的子阵列进行合并,
3. 组合:将两个排序的子阵列合并为一个排序列表.

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

1. 除以:首先重新排列,然后将数组拆分为2个子阵列,
2. 征服:递归地对生成的子阵列进行快速排序,
3. 合并:无.

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