algorithm - 快速排序，其中数组中的第一个元素较小

Question

考虑一个元素数组 {10,5,20,15,25,22,21}。

---

在这里，我将主元元素设为 21(数组中的最后一个)。根据我在互联网上看到的大多数快速排序算法，他们解释说从第一个元素开始与基准元素进行比较。如果它更小，它将与索引元素交换。但是算法在数组中有第一个小元素时中断，这让我很难写下快速排序将经历的中间步骤。互联网上的所有人都用第一个元素大于主元的数组示例进行了解释，因此在比较时他们没有交换并移动到下一个元素。

请帮忙。

Answer 1

我对如何理解快速排序的建议:

理解快速排序的关键是partition过程，它通常是一个for循环。请记住:

1. 我们的目标是在循环结束时让数组最终变成一个由三部分组成的数组:第一部分小于pivot，第二部分等于或大于枢轴，最后一部分是未排序的部分(没有元素)。
2. 在循环的最开始，我们也有三个部分:第一部分(没有元素)小于枢轴，第二部分(没有元素)等于或大于枢轴，最后一部分是未排序的部分(具有 array.length-1 元素)。
3. 在循环中，我们根据需要进行比较和交换，以确保在每个循环中，我们总是有这三个部分，并且第一部分和第二部分的大小在增加，并且大小最后一部分正在减少。

根据您在评论中的要求:

检查此链接:https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf

请仔细阅读三个示例图并确保您已理解它们。