快速排序QuickSqrt
<p>以下是我对快排的理解：</p><h2 id="一概念"><strong>一.概念</strong></h2>
<p> 快速排序采用分治法，每一次函数的递归都规定左右界限，并且以一个哨兵为基础，然后想办法让这个哨兵左边的值都小于哨兵，右边的值大于哨兵。</p>
<h2 id="二实现方法"><strong>二.实现方法</strong></h2>
<p> 其实就是不断挖坑的场景，在新的函数开始时，将取最左侧界限的值为哨兵，将它暂存起来，之后我们先从右到左寻找一个比哨兵小的值（每一次寻找，左侧界限不动，右侧界限向左收缩），然后将符合条件的值填入左侧界限。然后将左侧界限向后移动，形成新的左侧界限。<br>
然后我们开始从左到右寻找一个比哨兵大的值（每一次寻找右侧界限不动，左侧界限向右收缩），然后存放到右侧界限当中去（放心存，因为右侧界限没有动，并且右侧界限的值已经被存放到了之前的左侧界限中）。之后我们将右侧界限向左移动，构成新的右侧界限。<br>
然后进行循环收缩，直至i == j（左右界限相等）。<br>
在函数的最后，我们的左右界限到达了同一位置，此时已经满足了左侧界限前的值小于哨兵，右侧界限的值大于哨兵，并且当前<br>
左右侧界限相等到了一块，然后将一开始暂存的哨兵值填入当前所在位置。<br>
At the end of this function 我们递归调用快排函数，将当前区间一分为二，先递归左侧部分，也就是区间。<br>
之后再处理右侧部分,也就是区间。</p>
<h2 id="三概念图片"><strong>三.概念图片</strong></h2>
<p><img src="https://img2024.cnblogs.com/blog/3349629/202506/3349629-20250612222949872-101786104.jpg" alt="" loading="lazy"><br>
<img src="https://img2024.cnblogs.com/blog/3349629/202506/3349629-20250612223000495-1830560417.jpg" alt="" loading="lazy"></p>
<h2 id="四代码实现"><strong>四.代码实现</strong></h2>
<details>
<summary>点击查看代码</summary>
<pre><code>void QuickSort(int arr[], int left, int right)
{
int i, j, temp;
if (left < right) {
i = left, j = right;
//temp做哨兵
temp = arr;
//每一次循环保证左侧界限小于右侧
while (i < j) {
//从右向左寻找第一个小于哨兵的值
while (i < j && arr >= temp) {
j--;
}
//找到了后将值填入左侧界限的位置，并且更新左界限
if (i < j) {
arr = arr;
}
//从左向右寻找第一个大于哨兵的值
while (i < j && arr < temp) {
i++;
}
//将值填入右侧界限的位置，并且更新右界限
if (i < j) {
arr = arr;
}
}
//i==j了，其左侧和右侧都满足了快排的条件，我们将原来的哨兵的值给当前的位置
arr = temp;
//此时我们将当前区间的数组一分为二，先处理左侧，再处理右侧
QuickSort(arr, left, i - 1);
QuickSort(arr, i + 1, right);
}
}
</code></pre>
</details><br><br>
来源：https://www.cnblogs.com/xiaobai1523/p/18926248
頁:
[1]