分区排序与快速排序有何区别？

Question

分区排序和快速排序有什么区别？

- tony

Answer 1

快速排序是一种分区排序算法，你可能会参考归并排序，它也是一种分区排序算法，最大的区别可能在于速度，尽管它们都是O(n*log(n))。

快速排序使用一个枢轴元素进行排序，而归并排序则是分治法。然而，两者都是原地排序算法，这意味着它们在排序时不使用任何额外的内存。

- Filip Ekberg

---

当我看到“分区排序”时，我立刻想到，“如果他正在将其与QuickSort进行对比，那么他一定是指Mergesort。” +1 - 优秀的回答 - Mark Brittingham

归并排序不是一种原地排序算法：归并排序需要复制数组才能执行合并。维基百科上说：“归并排序的最常见实现不是原地排序”。虽然有一种优化方法只分配大小为N/2的数组，但仍然不是原地排序。此外，尽管快速排序在实践中通常更快，但归并排序具有理论上更紧密的上限运行时间。快速排序在最坏情况下是O(n2)，而不是O(nlog(n))。 - dantiston

Answer 2

在快速排序算法中有一个步骤是分割，它的作用是将数组中的一个元素放置在所有比它大的元素（在它的右侧子数组中）和所有比它小的元素（在它的左侧子数组中）之间。

- Ofek Ron

---

+1 很好的信息。请记住，在标记为“作业”的问题中，目标是提供指导而不是具体答案。 - Chains