快速排序是一种分治算法吗？

Question

1. I consider Merge sort as divide and conquer because,

   Divide - Array is literally divided into sub arrays without any processing(compare/swap), and the problem sized is halved/Quartered/....

   Conquer - merge() those sub arrays by processing(compare/swap)

   Code gives an impression that it is 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. But in Quick sort,

   Firstly, Complete array is processed(compare/swap) using a partition element(pivot) and fix the final position of pivot, and then problem size is halved/Quartered/.... for re-partitioning,

   Code does not give an impression of divide & conquer,

   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阶段的理解是指减少（一半）问题规模。在快速排序中，您是否将使用枢轴对数组进行处理（比较/交换）并分区视为Divide阶段？

2. Conquer阶段的理解是指收集/合并回来。在快速排序中，conquer阶段是什么意思？

---

            Note: Am a beginner, in sorting algorithms

- overexchange

---

也许可以添加“语言无关”的标签？ - Joseph Wood

@JosephWood 我添加了 C 语法。 - overexchange

欢迎您自由地解释这种语言的意思，就像“万能士·杜普提”里所描述的一样。并不是每个人都会同意你认为这些词应该表达的意思。如果你已经知道答案，那么为什么还要问呢？我想我们应该把它归类为“主观性强”的问题，因为有两种不同的解释方式。（在我看来，划分步骤大致上将问题分成了两个近似相等的部分，每个部分都采用同样的方式进行处理——完全是一种分而治之的技术。） - Jonathan Leffler

明确回答您的问题：1. 在快速排序中，划分步骤是划分过程。2. 两个递归调用是征服步骤。相比之下，归并排序需要在递归调用中征服后进行额外的“未划分”（merge）步骤。 - Jonathan Leffler

@JonathanLeffler conquer的意思是什么？对我来说，它就像是聚集/合并。因此，我会说，递归调用sort(a, lo, j-1);在语法上解决了一半的问题（j-1是第一个枢轴元素的左侧立即位置）。 - overexchange

Answer 1

分治算法有三个阶段：

1. 分割，
2. 解决，
3. 合并。

对于归并排序（http://www.cs.umd.edu/~meesh/351/mount/lectures/lect6-divide-conquer-mergesort.pdf）：

1. 分割：将数组分成两个子数组，
2. 解决：递归地归并排序产生的子数组，
3. 合并：将两个排序好的子数组合并为一个排序好的列表。

对于快速排序（https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf）：

1. 分割：首先重新排列数组，然后将其分成两个子数组，
2. 解决：递归地快速排序产生的子数组，
3. 合并：无。

注意：感谢罗切斯特大学和马里兰大学计算机科学系。

- Erkan Hatipoglu

---

如果你看代码，快速排序不是先将数组分割成两个部分。首先，partition(a, lo, hi); 用给定的枢轴将元素进行分区。接下来，通过 sort(a, lo, j-1); 在稍后将数组分成两部分。 - overexchange

分区操作是一种分割操作。在快速排序的一个有效实现中，“合并”操作可以被视为将两个数组附加在一起，但这在“原地”排序中是不必要的。 - vzn