Hello,大家好,今天分享的八大排序里的快速排序,所谓快速排序是一个叫霍尔的人发明,有很多人可能会觉得为什么不叫霍尔排序,其中原因就是因为它快,快速则体现了它的特点,今天我们就来讲一下快速排序,现在开始我们的学习吧。
快速排序
1.基本思想
通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
实现逻辑
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
① 从数列中挑出一个元素,称为 “基准”(pivot),
② 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③ 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
我们来看一下它的图是怎么实现的
首先我们给定它一个数组,并且定义左边为left,右边为right,然后我们的有个中间值,中间值这里我们就叫它为k,定义这个k是从left开始,当然我们也可以从right开始,等一下会来讲原因,现在我们只要看懂它的图就行
因为是从左边开始,所以要从右边先走,原因是我们这样才能确定left和right相遇的时候的值一定比k的值小,这里再详细展开讲解一下,我们的left和right相遇有两种可能,一种是left和right相遇,这个时候相遇是怎样的呢,因为right先走,遇到比k小的时候停下来,然后left又开始走,除非遇到比l大的值才会停下,否则就继续,但是我们还有一个结束条件那就是left要小于right,所以如果left没有找到比k大的值,他们就会相遇,那这样的话,因为我们right找到小的值了,所以最后k肯定比right所指向的值要大,还有一个就是我们right遇到left,那同样的道理,说明我们的right没有找到比k大的值,所以相遇之后也是一样的道理,结论就是相遇的值一定比k指向的值小。那我们再继续来看图
这个时候我们的right找到比k小的值,然后才开始动left,那我们现在开始动left
left也找到了,那现在就是交换它们的,这里我们用一个swap函数就可以了,因为后面还需要用到swap这个函数的,交换之后变成这样的
可以看到先在我们已经开始交换,我们找值需要一个两个while,外面还需要一个大while控制
那我们现在可以继续开始动right了
这下又找到了
开始动left
那现在我们需要交换他们
现在我们也交换好了,现在right在走一步就会爆炸(小编是小黑子,实锤了),这个时候循环就应该结束
我们需要做的就是在循环外面再进行k和left的交换
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
int k = left;
while (left < right)
{
while ( a[right] > a[k])
{
right--;
}
while ( a[left] < a[k])
{
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[k]);
return left;
}
这里其实会有问题,有两个问题,一个是会存在越界,一个就是会出现死循环,先讲一下死循环的例子,比如我们再第一次找left和right的值,这两个值的大小是相等的,那他们进行交换之后,left和right的值就不会变了,因为循环他们进不去了,所以要加一个等于的条件就行了,还有就是越界,我们之前讲过越界就像查酒驾一样,是有随机性的,为什么会越界,是因为right可能一直找不到小的值,然后就会比left还小,所以我们只需要加上一个条件就行了
看看代码
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
int k = left;
while (left < right)
{
while (left < right && a[right] >= a[k])
{
right--;
}
while (left < right && a[left] <= a[k])
{
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[k]);
return left;
}
现在就是这只是我们走了一遍并不能实现将他们变成有序数列,所以这里我们就可以用递归进行遍历,怎么进行遍历,为什么能进行遍历呢,我们来分析
会这样分成左边和右边,然后再左边和右边再进行我们上面的操作,那是不是和二叉树很 相似的,所以我们递归实现一下,这里不过多的讲解,等我更新二叉树的文章后,大家可能看起来就明白了
void QuickSort(int* a, int begin,int end)
{
if (begin >= end)
return;
int ret = PartSort(a, begin, end);
QuickSort(a, begin, ret - 1);
QuickSort(a, ret + 1, end);
}
完整代码加测试代码文章来源:https://www.toymoban.com/news/detail-703522.html
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
int k = left;
while (left < right)
{
while (left < right && a[right] >= a[k])
{
right--;
}
while (left < right && a[left] <= a[k])
{
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[k]);
return left;
}
void QuickSort(int* a, int begin,int end)
{
if (begin >= end)
return;
int ret = PartSort(a, begin, end);
QuickSort(a, begin, ret - 1);
QuickSort(a, ret + 1, end);
}
#include<stdio.h>
int main()
{
int arr[] = { 6,1,2,7,9,3,4,10,8 };
QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
printf("%d ", arr[i]);
}
return 0;
}
反正最后排序成功了,这个挡住了一部分结果,我换个大的
好好好,今天的学习就到这吧,拜拜。。。。文章来源地址https://www.toymoban.com/news/detail-703522.html
到了这里,关于八大排序——快速排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!