目录
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序作为一种高效排序
它采用了分治以及递归的方法去将我们所需要排序的数据进行有序排序
很多商场或者机构都会采用这种排序方法去进行有序排序
- 选择枢轴：首先在我们所需要便利的数据中选择一个元素作为枢轴，元素的选择有很多种，可以是中间值，随机值或者始末元素等等，更复杂的是采用三数中值法
- 分区： 一旦枢轴被选择完成后，数组会进行重新排列，所有比枢轴小的元素移动到枢轴的左边，所有比枢轴大的元素移动到右边。这个过程结束时，枢轴元素处于其最终排序后的正确位置。
- 递归： 接下来，快速排序算法递归地将左边和右边的子数组进行排序。递归的基准条件是子数组的大小为0或1，这意味着它们已经被排序了
1.分区操作
分区操作是快速排序算法中的核心步骤。它的目标是根据枢轴元素重新排列数组的部分区间，使得所有比枢轴小的元素都移到它的左边，而所有比枢轴大的元素都移到它的右边。在这个过程中，枢轴元素自身也找到了其在数组中的正确位置。这个步骤是递归进行排序的前提。下面详细解释这个过程：
设置指针：
设置两个指针，left指向数组的开始（或枢轴的下一个元素，取决于枢轴的选择），right指向数组的末尾。
指针移动和交换：
向右移动left指针：从left开始向右移动，直到找到一个大于或等于枢轴值的元素，向左移动right指针：从right开始向左移动，直到找到一个小于或等于枢轴值的元素
检查和交换：
如果left指针仍在right指针的左侧（即left < right），则交换left和right指向的元素，并继续移动指针。
递归的终止条件：
当left指针超过right指针，即left >= right时，分区操作结束。此时，所有比枢轴小的元素都在它的左边，而所有比枢轴大的元素都在它的右边
单趟的代码如下：
int left = begin;
int right = end;
int key = begin;
while (left < right)
{
while (left < right && a[right] >= a[key])
{
right--;
}
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]);
key = left;
初始化指针和枢轴：
left初始化为begin，这是当前考虑的数组段的起始位置right初始化为end，这是当前考虑的数组段的结束位置key用于记录枢轴的位置，这里选择的是数组段的第一个元素作为枢轴，因此key初始化为begin
2.分区过程：
●外层循环：while (left < right)确保当左右指针相遇或交错时，循环停止。这意味着分区过程完成。
●右侧扫描：第一个内层循环while (left < right && a[right] >= a[key])从右向左移动right指针，寻找第一个小于枢轴值a[key]的元素。
●左侧扫描：第二个内层循环while (left < right && a[left] <= a[key])从左向右移动left指针，寻找第一个大于枢轴值a[key]的元素。
●交换：Swap(&a[right], &a[left])交换左右指针所指向的元素。这次交换是为了把小于枢轴值的元素移动到枢轴的左侧，大于枢轴值的元素移动到枢轴的右侧
3.枢轴归位：
●循环结束时，left和right指针相遇。此时，left指针的位置就是枢轴元素应该所在的最终位置。（这里下面再做解释）●Swap(&a[left], &a[key])交换枢轴元素与left指针所指的元素。这步确保了枢轴元素被放置在其正确的位置，即所有左侧元素都不大于它，所有右侧元素都不小于它●最后，将key更新为left，尽管在这个代码片段中，这个赋值操作对于后续流程并不是必需的，因为key的值在这之后没有再被使用。如果这是分区函数的一部分，key（或者这里应该是left）的新值可能会被用来指示下一步递归操作的分界点。
2.相遇位置小于枢轴元素
但是我们需要注意一下特殊情况
分多种情况进行讨论：
这里我们就可以分多种情况进行讨论：
●right遇到left：注意，代码中我们是先让right移动的，意味着left所指向的是上一此交换后小于枢轴元素的数，所以当相遇后，key与left交换，left指向的元素一定小于key指向的元素●left遇到right：由于right先动，意味着right已经找到了一个比key小的元素，当left遇到right使，此时right，left指向的元素一定小于key指向的元素。
一旦枢轴元素被放置在其正确位置上，数组就被分成了两部分。左边的子数组包含了所有小于枢轴的元素，而右边的子数组包含了所有大于枢轴的元素。这时，独立地对左右两个子数组应用同样的快速排序过程。这就是递归的步骤，因为同一个过程被用来排序较小的数组
3.递归终止条件
●递归的终止条件是子数组的大小减到0或1，这时不需要做任何操作：
●大小为0的子数组意味着在分区过程中，没有元素被划分到某一侧。例如，如果枢轴是最小（或最大）元素，并且所有其他元素都被划分到了枢轴的另一侧，那么这一侧实际上就没有元素，子数组的长度为0
●大小为1的子数组意味着在分区过程结束后，某一侧只有一个元素。由于任何单一元素的集合自然是已排序的（因为没有其他元素可以与之比较大小），这意味着不需要对这样的子数组进行进一步的排序操作
void Quicksort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = begin;
while (left < right)
{
while (left < right && a[right] >= a[key])
{
right--;
}
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]);
key = left;
Quicksort(a, begin, key - 1);
Quicksort(a, key + 1, end);
}
●递归的终止条件：if (begin >= end)检查当前的子数组是否已经是不可分割的，即长度为0或1。如果满足这个条件，函数就会直接返回，不再继续执行后续的排序操作
●初始化变量：变量left和right被初始化为子数组的起始和结束索引。变量key作为枢轴的索引也被初始化为begin，即子数组的第一个元素
代码如下：
void Quicksort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = begin;
while (left < right)
{
while (left < right && a[right] >= a[key])
{
right--;
}
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]);
key = left;
Quicksort(a, begin, key - 1);
Quicksort(a, key + 1, end);
}
●递归的终止条件：if (begin >= end)检查当前的子数组是否已经是不可分割的，即长度为0或1。如果满足这个条件，函数就会直接返回，不再继续执行后续的排序操作
●初始化变量：变量left和right被初始化为子数组的起始和结束索引。变量key作为枢轴的索引也被初始化为begin，即子数组的第一个元素
4.代码优化：三数取中法
三数取中法是在实现快速排序时用来提高性能并降低遇到最坏情况概率的一种技术。该方法通过选择一个较为接近中值的枢轴元素来分区数组，以避免每次都产生不平衡的分区，从而增加算法的效率
在三数取中法中，我们通常取数组中以下三个值：
1.起始值（通常是数组的第一个元素）
2.结束值（通常是数组的最后一个元素）
3.中间值（数组中间位置的元素，可以通过(begin + end) / 2计算得出）
4.然后，比较这三个元素的大小，并选择处于中间大小的元素作为枢轴元素。这样做的目的是尽量避免选择最小或最大的元素作为枢轴，因为这会产生不平衡的分区。这个选取枢轴的过程实际上是一个非常简单的大小比较和交换操作
三数取中法选取key的具体实现可能如下：
int Getmidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] < a[begin])
return end;
else
return begin;
}
}
void Quicksort(int* a, int begin,int end)
{
if (begin >= end)
{
return;
}
int midi = Getmidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int left = begin;
int right = end;
int key = begin;
while (left < right)
{
while (left<right && a[right]>=a[key])
{
right--;
}
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]);
key = left;
Quicksort(a, begin, key - 1);
Quicksort(a, key+1, end);
}
函数Getmidi尝试从数组的begin、end和midi（中间）位置选取一个"中间值"（不是数值上的中位数，而是在三个数中大小排在中间的数）。然后，Quicksort1函数利用三数取中的方法来选择枢轴元素(key)并执行快速排序过程。
Getmidi 函数详解：
Getmidi函数通过比较三个位置（起始位置、中间位置和结束位置）的元素大小来返回中间值的索引。这里的中间值是指这三个元素中不是最大也不是最小的那个。判断条件覆盖了所有可能的大小顺序，来确保正确选取中间值。
5.挖坑法实现快排
挖坑法是实现快速排序的一种方法，它简化了元素交换的步骤，通过"挖坑填数"来完成元素的位置调整。这个方法的基本思想是选定一个枢轴值（pivot），然后将小于枢轴值的元素移动到枢轴的左边，将大于枢轴值的元素移动到枢轴的右边，最终将枢轴值放入正确的位置。
下面是使用挖坑法实现快速排序的示例代码：
void QuickSortHole(int* arr, int begin, int end) {
if (begin >= end) {
return; // 递归结束条件
}
int key = arr[begin]; // 选取第一个元素作为枢轴
int left = begin;
int right = end;
while (left < right) {
// 从右向左找到第一个小于枢轴的元素，填入左边的坑
while (left < right && arr[right] >= key) {
right--;
}
arr[left] = arr[right]; // 将找到的较小元素填到左边的坑里，此时右边形成一个新的坑
while (left < right && arr[left] <= key) {
left++;
}
arr[right] = arr[left];
}
arr[left] = key;
QuickSortHole(arr, begin, left - 1);
QuickSortHole(arr, left + 1, end);
}
先将第一个数据存放在临时变量key中形成一个坑位
让我们通过一个具体的例子来解释挖坑法如何在快速排序中工作。假设我们有以下数组：
[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
我们要对这个数组进行快速排序。选择第一个元素作为枢轴值（pivot），这里是6。我们现在开始挖坑法的过程：
初始化：枢轴值为6，因此数组的第一个位置成了一个“坑”，我们用这个“坑”来存放接下来找到的符合条件的元素。此时数组状态和指针位置如下：
[6*, 1, 2, 7, 9, 3, 4, 5, 10, 8] // *表示坑位
left right
从右向左扫描：找到第一个小于6的元素，这里是5。我们将5放入左边的“坑”中，并将5的位置变成新的“坑”。数组现在看起来是这样：
[5, 1, 2, 7, 9, 3, 4, 6*, 10, 8] // 将5移动到左边的坑位，6的位置成为新的坑位
left right
从左向右扫描：找到第一个大于6的元素，这里是7。我们将7放入右边的“坑”中，并将7的位置变成新的“坑”。数组更新为：
[5, 1, 2, 6*, 9, 3, 4, 7, 10, 8] // 将7移动到右边的坑位，6的位置再次成为新的坑位
left right
重复这个过程，直到left和right指针相遇。在这个例子中，当两个指针相遇时，我们发现它们都指向了索引3的位置（现在是一个“坑”），这个位置正是枢轴值6最终应该放置的位置。所以，我们把枢轴值放回这个“坑”里。数组现在是：
[5, 1, 2, 6, 9, 3, 4, 7, 10, 8]
此时，枢轴值6已经放到了它最终的位置上，所有在它左边的元素都比它小，所有在它右边的元素都比它大。现在，我们对6左边和右边的子数组递归执行相同的排序过程。
这种方法减少了元素的直接交换，通过移动“坑”位置来调整元素的位置
当然我们也可以继续使用三数取中法选key对代码再次优化：
void QuickSortHole(int* arr, int begin, int end) {
if (begin >= end) {
return;
}
int midi = Getmidi(arr, begin, end);
Swap(&arr[midi], &arr[begin]);
int key = arr[begin];
int left = begin;
int right = end;
while (left < right) {
while (left < right && arr[right] >= key) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= key) {
left++;
}
arr[right] = arr[left];
}
arr[left] = key;
QuickSortHole(arr, begin, left - 1);
QuickSortHole(arr, left + 1, end);
}
6.前后指针实现快排
void QuickSort3(int* arr, int begin, int end) {
if (begin >= end) {
return;
}
int keyi = Getmidi(arr, begin, end);
Swap(&arr[keyi], &arr[begin]);
int key = arr[begin];
int cur = begin + 1;
int pre = begin;
for (; cur <= end; ++cur) {
if (arr[cur] < key) {
++pre;
Swap(&arr[pre], &arr[cur]);
}
}
Swap(&arr[begin], &arr[pre]);
QuickSort3(arr, begin, pre - 1);
QuickSort3(arr, pre + 1, end);
}
设置指针
设置两个指针cur（当前指针）和pre（前指针）。cur从枢轴元素的下一个位置开始，即begin + 1，而pre从枢轴元素的位置开始，即begin。这样设置是为了准备遍历数组进行分区。
遍历与交换
遍历数组从cur到end的所有元素。对于每个元素，比较其与枢轴元素的大小：
如果当前cur指向的元素小于枢轴元素，则表示这个元素应该位于枢轴的左侧。
为了将其移动到正确位置，首先将pre指针向右移动一个位置（即++pre），然后交换pre和cur指向的元素的位置。这一步确保了pre左侧的所有元素（包括pre指向的元素）都不大于枢轴元素。
枢轴归位
遍历结束后，pre指向的是最后一个小于枢轴的元素的位置。由于初始时枢轴元素被置于数组的起始位置（即begin），现在需要将枢轴元素与pre指向的元素进行交换。
这样做的结果是，枢轴元素被放置到了其最终的正确位置上。至此，枢轴元素的左侧都是不大于它的元素，右侧都是不小于它的元素。
