大家好，我是小卡皮巴拉
文章目录
目录
引言
一. 快速排序的基本思想
二. 快速排序实现主框架
三.寻找基准值的几种方法
hoare版本
挖坑法
前后指针版本
兄弟们共勉 ！！！
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
引言
在数据处理的魔法世界里，有一种算法如同一位技艺高超的魔术师，能在瞬间将杂乱无章的数据变得井井有条。它，就是快速排序（QuickSort）——一个既高效又充满魅力的排序算法。
想象一下，你面对着一堆毫无规律的数字或字母，如何在最短的时间内将它们排列得整整齐齐？快速排序就是这样一位神奇的助手，它运用分治法的智慧，通过巧妙地选择一个基准元素，将复杂的问题分解成更小的子问题，然后逐个击破。
快速排序不仅速度快，而且实现起来也相对简单。它的平均时间复杂度达到了令人惊叹的O(n log n)，在处理大规模数据时更是游刃有余。尽管在最坏的情况下，它的性能会有所下降，但只要我们稍微动点心思，选择合适的基准元素，就能让它始终保持在最佳状态。
那么，这位数据排序的魔术师究竟是如何施展它的魔法的呢？接下来，就让我们一起揭开快速排序的神秘面纱，探索它背后的工作原理和奇妙之处吧！
一. 快速排序的基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
简单的来说，快速排序就是：
拿出一个元素当标杆，然后把其他元素分成两堆，一堆比标杆小，一堆比标杆大。接着，对这两堆再分别找出标杆，继续分堆。这样一直分下去，直到每堆都只有一个元素，最后按顺序把堆合并起来，就排好序了。
二. 快速排序实现主框架
我们在这里用函数的递归调用来实现快速排序的主框架：
void QuickSort(int* arr, int left, int right) {
// 若区间元素小于等于1个，直接返回，已有序
if (left >= right) {
return;
}
// 找基准值并划分区间，获取基准值最终索引
int keyi = _QuickSort1(arr, left, right);
// 递归对基准值左边子区间排序
QuickSort(arr, left, keyi - 1);
// 递归对基准值右边子区间排序
QuickSort(arr, keyi + 1, right);
}这段快速排序主框架代码通过递归实现对给定数组指定区间的排序。首先，若区间元素小于等于 1 个（即left >= right），则该区间已有序，直接返回以终止当前递归。接着，调用_QuickSort1函数选取基准值并对区间进行划分，keyi记录基准值的最终位置。最后，分别对基准值左右子区间递归调用QuickSort函数，持续划分和排序子区间，直至所有子区间元素有序，从而实现整个区间的排序。
将区间中的元素进行划分的 _QuickSort 方法主要有以下几种实现方式：
三.寻找基准值的几种方法
hoare版本
算法思路
Hoare 版本找基准值，先选区间首元素为基准。设左指针于第二个元素，右指针于末尾。右指针左移找小于基准的，左指针右移找大于基准的，找到就交换。如此循环直至两指针相遇，再将基准与相遇处元素互换，这样基准就位，数组也分成左右两部分，左边小于等于基准，右边大于等于基准。
具体做法
选择基准元素
通常选择待排序区间的第一个元素作为基准值
key，先把它的值记录下来，方便后续比较操作。设定双指针
- 左指针
left：一开始指向待排序区间的第二个元素（因为第一个元素已选为基准值）。- 右指针
right：指向待排序区间的最右边元素。开始移动指针并交换元素
从右往左找小于基准值的元素：
右指针right先行动，从右往左扫描数组。只要right指向的元素大于等于key，就继续往左移动right指针，直至找到一个小于key的元素。从左往右找大于基准值的元素：
当右指针right找到小于key的元素后，左指针left从其当前位置从左往右扫描数组，只要它指向的元素小于等于key，就继续往右移动left指针，直到找到一个大于key的元素。交换元素：
当左指针left和右指针right都找到符合条件（左大右小）的元素后，交换这两个元素的位置。然后重复上述从右往左、从左往右找元素以及交换的过程。确定基准值最终位置
该过程持续到左指针
left和右指针right相遇或者交叉（即left >= right）。此时它们相遇的位置就是基准值key的最终正确位置。最后把一开始记录的基准值key放到这个相遇的位置上，这样一趟下来，数组就被划分成了左边部分元素都小于等于key，右边部分元素都大于等于key的状态了，也就成功找到了基准值的位置并且完成了初步的区间划分。
下面我们来思考在这个过程中存在的两个问题：
问题1：为什么跳出循环后right位置的值一定不大于key？
当left > right 时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key
问题2：为什么left和right指定的数据和key值相等时也要交换？
相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。
动图助解：
这里使用了博主 @五分钟学算法之快速排序 的图片，如有侵权，请联系我删除哈。
代码实现：
int _QuickSort(int* arr, int left, int right)
{
// 选当前区间最左元素作基准值索引，先记录下来
int keyi = left;
// 让左指针跳过基准值位置
++left;
// 通过双指针从两端扫描调整元素实现区间划分
while (left <= right)
{
// 从右往左找比基准值小的元素，符合条件则右移指针
while (arr[right] > arr[keyi] && left <= right)
{
right--;
}
// 从左往右找比基准值大的元素，符合条件则左移指针
while (arr[left] < arr[keyi] && left <= right)
{
left++;
}
// 若左右指针未交错，交换对应元素并移动指针
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
// 交换基准值与right指向元素，确定基准值最终位置
Swap(&arr[keyi], &arr[right]);
// 返回基准值最终索引，供后续确定子区间用
return right;
}挖坑法
算法思路
挖坑法找基准值，先把区间首个元素当作基准值并保存，此位置成 “坑”。设左指针在第二个元素，右指针在末尾。右指针左移找小于基准的元素，找到后填到 “坑” 里，该位置成新 “坑”；左指针右移找大于基准的元素，找到后填到新 “坑”，此位置又成新 “坑”。如此反复，直至两指针相遇，把保存的基准值填入相遇处，基准值归位，数组也划分成左右两块，左边小于等于基准，右边大于等于基准。
具体做法
选择基准元素
选取待排序区间首个元素作基准值，记为
key并保存，原位置形成 “坑”。设定双指针
- 左指针
left：指向区间第二个元素。- 右指针
right：指向区间最右边元素。开始移动指针并填坑、挖坑操作
从右往左找小于基准值的元素：
right从右往左扫描，若元素大于等于key则继续左移，找到小于key的元素后，将其填到left指向的 “坑”，right处变为新 “坑”。从左往右找大于基准值的元素：
left从左往右扫描，若元素小于等于key则继续右移，找到大于key的元素后，填到right指向的 “坑”，left处变为新 “坑”。持续填坑、挖坑过程：
重复上述操作，左右指针交替工作，调整元素位置。确定基准值最终位置
持续操作直至
left与right相遇，将key填到相遇位置，此时数组按要求划分好，确定了基准值位置与区间划分。
动图助解：
代码实现：
int _QuickSort1(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
//从右往左找出比基准小的数据
while (left < right && arr[right] >= key)
{
right--;
}
//找到后立即放入左边坑中
arr[hole] = arr[right];
//当前位置变为新坑
hole = right;
//从左往右找出比基准值大的数据
while (left < right && arr[left] <= key)
{
left++;
}
//找到后立即放入右边的坑中
arr[hole] = arr[left];
//当前位置变为新坑
hole = left;
}
arr[hole] = key;
return hole;
}前后指针版本
算法思路
前后指针法找基准值，先取区间首元素作基准。前指针在第二元素，后指针在第三元素。后指针后移扫描，遇小于基准元素，前指针先移一位，再与后指针元素交换，后指针继续后移。直至后指针遍历完区间，把前指针元素与基准交换，该位置即基准正确位置，数组以此分界，左小于等于基准，右大于等于基准。
具体做法
选择基准元素
选取待排序区间的首元素作为基准值，将其记为
key并保存。设定指针
- 前指针
prev：初始指向待排序区间的第二个元素。- 后指针
cur：初始指向待排序区间的第三个元素。移动指针并调整元素
- 后指针扫描数组：
后指针cur从初始位置开始向后扫描数组。每扫描到一个元素，就将其与基准值key进行比较。- 依据比较结果处理元素：
如果当前cur指向的元素小于基准值key，则将前指针prev先向后移动一位（若prev与cur不重合），然后交换prev和cur所指向的元素，之后cur继续向后移动。这样做的目的是将小于基准值的元素不断交换到前面，使前指针之前的元素都小于基准值。- 持续移动与调整：
后指针cur持续向后移动并重复上述比较与交换操作，直至cur遍历完整个区间。确定基准值最终位置
当后指针
cur遍历完整个区间后，将前指针prev所指向的元素与基准值key进行交换。此时，前指针prev所在位置就是基准值的最终正确位置。
动图助解：
我们还需要注意以下的问题
为什么限制条件要加上cur != ++prev
因为交换前prev要先走向下一个位置，此时刚好和cur重合，此时交换是无意义的，应该让cur继续移动。
为什么要先让prev++，再与cur交换
因为prev所在位置是已经调整好的数据，所以要先让prev先移动到下一个位置。
兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
