快速排序QuickSqrt

祝娜娜 · 2025-6-18 09:29:21

以下是我对快排的理解：
一.概念

快速排序采用分治法，每一次函数的递归都规定左右界限，并且以一个哨兵为基础，然后想办法让这个哨兵左边的值都小于哨兵，右边的值大于哨兵。
二.实现方法

其实就是不断挖坑的场景，在新的函数开始时，将取最左侧界限的值为哨兵，将它暂存起来，之后我们先从右到左寻找一个比哨兵小的值（每一次寻找，左侧界限不动，右侧界限向左收缩），然后将符合条件的值填入左侧界限。然后将左侧界限向后移动，形成新的左侧界限。
然后我们开始从左到右寻找一个比哨兵大的值（每一次寻找右侧界限不动，左侧界限向右收缩），然后存放到右侧界限当中去（放心存，因为右侧界限没有动，并且右侧界限的值已经被存放到了之前的左侧界限中）。之后我们将右侧界限向左移动，构成新的右侧界限。
然后进行循环收缩，直至i == j（左右界限相等）。
在函数的最后，我们的左右界限到达了同一位置，此时已经满足了左侧界限前的值小于哨兵，右侧界限的值大于哨兵，并且当前
左右侧界限相等到了一块，然后将一开始暂存的哨兵值填入当前所在位置。
At the end of this function 我们递归调用快排函数，将当前区间一分为二，先递归左侧部分，也就是区间[left，i-1]。
之后再处理右侧部分,也就是区间[i+1，right]。
三.概念图片

四.代码实现

点击查看代码

void QuickSort(int arr[], int left, int right)
{
int i, j, temp;
if (left < right) {
i = left, j = right;
//temp做哨兵
temp = arr[left];
//每一次循环保证左侧界限小于右侧
while (i < j) {
//从右向左寻找第一个小于哨兵的值
while (i < j && arr[j] >= temp) {
j--;
}
//找到了后将值填入左侧界限的位置，并且更新左界限
if (i < j) {
arr[i++] = arr[j];
}
//从左向右寻找第一个大于哨兵的值
while (i < j && arr[i] < temp) {
i++;
}
//将值填入右侧界限的位置，并且更新右界限
if (i < j) {
arr[j--] = arr[i];
}
}
//i==j了，其左侧和右侧都满足了快排的条件，我们将原来的哨兵的值给当前的位置
arr[i] = temp;
//此时我们将当前区间的数组一分为二，先处理左侧，再处理右侧
QuickSort(arr, left, i - 1);
QuickSort(arr, i + 1, right);
}
}

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

快速排序QuickSqrt

浏览过的版块

签约作者