文章目录
前言一、(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。二、(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。三、(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。四、(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。五、总结六、代码实现
前言
快速排序算法通过多次比较和交换来实现排序，其排序流程如下： (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
此解释源自百度百科
接下来我一句一句的解释这四句话
一、(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
我们以这几个数字为例。我们要选定一个分界值（这个过程非常简单，可以采取三数取中的方法）这篇博客的重心在于介绍快排的思想，我们就简单的以第一个数字(6)为分界值吧。
二、(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
我们接下来要做的是将数组中大于等于6的数据集中到数组右边，小于分解值的数据集中到数组左边，那么怎么实现这个过程呢？
我们会设置两个指针，分别指向数组的左边和数组的右边。然后将两个指针不断的向中间逼近。直到它两吻合。 对于j指针而言，它要不断向左走。它的目标是找到比6小的数据，如果找到了的话就停下来。 对于指针i而言，它要不断向右走，它的目标是找到比6大的数据，如果找到的话就停下来。 然后交换i指针指向的数据和j指针指向的数据。
到这里，第一次交换就结束了，但是任务仍未结束，我们仍然无法确定两个指针中的数据满足条件。i继续向右走，j继续向左走
在这，i继续指向了大于6的数，重复上述操作。 交换完成后，j继续往左走，i继续往右走
此时出现了一种状况：j指向了小于分界值的数据，但i没有。但是i与j已经相遇了。此时它们相遇点的数据必定是小于分界值的。因为我们要让j先走，j遇到小于分界值的数据就会停下来。j走完才会让i走。最终相遇时就一定是小于分界值的数据。这时，我们将分界值的数据与相遇点的数据交换。 此时，我们就完成了单趟排序，即比分界值小的值都在它的左边，比分界值大的值都在它的右边。同时我们可以认为，分界值已经在它正确的位置了。
三、(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
到这里，我们对上一步分界值的左边一部分数据进行与第二步类似的处理。 一、选出分界值。 二、将小于分界值的数据放到左边，大于分界值的数据放到右边。
四、(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
五、总结
在上述过程中，有几个需要注意的点。 1.必须要让j先走。这是为了确保i和j相遇时指向的一定是比分界值小的数。 2.单趟排序之后，分界值就到了它应该到的位置（这句话的意思理解一下就是：这个分界值已经到了终点了。后续也不会再管它了）
六、代码实现
void Quick_Sort(int *arr, int begin, int end){
if(begin > end)
return;
int tmp = arr[begin];
int i = begin;
int j = end;
while(i != j){
while(arr[j] >= tmp && j > i)
j--;
while(arr[i] <= tmp && j > i)
i++;
if(j > i){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[begin] = arr[i];
arr[i] = tmp;
Quick_Sort(arr, begin, i-1);
Quick_Sort(arr, i+1, end);
}
发表评论