本文共 2633 字,大约阅读时间需要 8 分钟。
快速排序在排序中占有重要的地位,今天我和你一起来学习一下快速排序究竟有什么魅力可以让大家使用!
我们先看看快速排序的基本步骤:
假设有n个变量的数组S[n]
1.首先设置两个变量i,j,设置i = 0,j = n-1;
2.我们要找到一个类似中间值的数据为关键数据,可以设为S[0],更好的是找到一个更接近中间值的数来进行处理,可以进行优化。
3.第三步是关键,分为两步
1)从最后的元素A[n-1]向前寻找,j--,找到一个小于Key关键数据的值,此时为A[j]来表示,将A[i](此时i还是0)的值与A[j]进行交换,此时就把一个比关键词Key小的值放在了Key的左边,并使得Key的位置变为A[j].
2)从最前的元素A[0]开始查找,i++,寻找比Key值大的数据,此时可以说是A[i],然后将A[i]和A[j]的值进行交换,此时Key值在A{i]的位置,并把一个比Key值大的值放在Key的右边。
4.重复3步骤,直到i=j,找不到比Key小或者大的时候使j=j-1;i=i+1;进行循环。
具体演示为:
A[12] = {4,15,8,14,2,21,10,3,19,9,22,8};
-----0步准备
{4,15,8,14,2,21,10,3,19,9,22,8};
----------1步
i=0,j=11,k=4;
{
4,15,8,14,2,21,10,3,19,9,22,8};找到第一个比key4小的值A[j],将A[i]和A[j]的值交换
{
3,15,8,14,2,21,10,4,19,9,22,8};------------------2步
i = 0, j = 7;key = 4;
将i值向前走,i++找到第一个比key=4大的值
将A[i]和A[j]的值进行交换得到:
{3,4,8,14,2,21,10,15,19,9,22,8};
-----------------以上就是一个循环步骤------------------------------------
接着继续循环j--比较:
{3,4,8,14,2,21,10,15,19,9,22,8};交换:
{3,2,8,14,4,21,10,15,19,9,22,8};
i++:
{3,2,4,14,8,21,10,15,19,9,22,8};
j--:{3,2,4,14,8,21,10,15,19,9,22,8}
i==j成立!
------------------------以上为第二个循环步骤------------------------------------
接着j--循环直到i==j也没找到比key=4小的值,结束该循环
判断和循环一起进行。
此时key =4把数据分为两组:
小于key| |大于key
{3,2,4,14,8,21,10,15,19,9,22,8}
分别递归循环3步骤,即:
--------------------------------------------------------------------------------------------------小于Key=4
小于Key :{3,2}----->>>>>>>>{ 2, 3}
-----------------------------------------------------------------------------------------------------大于Key =4
大于Key:
{14,8,21,10,15,19,9,22,8};
Key = 14;j红色位置 i 绿色位置
j--:{8,8,21,10,15,19,9,22,14}(找到8小于14,并交换,下同)
i++:{8,8,14,10,15,19, 9, 22,21}
j--:{8,8,9,10,15,19,14,22,21}
i++:{8,8,9,10,14,19,15,22,21}
Key
------------------------------------第三轮
-----------------------------------------------------------------------------------------------------小于Key =14
{8,8,9,10}结束
-----------------------------------------------------------------------------------------------------大于Key =14
{19,15,22,21}
Key =19;j红色位置 i 绿色位置
j--: 15192221
------------------------------------------第四轮
j红色位置 i 绿色位置
-----------------------------------------------------------------------------------------------------大于Key =19
{22,21}
j--: {
21,22}结束!
------------------------------------------------C++代码解析----------------------------------------------------------------------------------
参考百度百科代码。
#includeusing namespace std;void Qsort(int a[], int i, int j){ if(i >= j) { return; } int first = i; int last = j; int key = a[i];/*用字表的第一个记录作为枢轴Key*/ while(first < last) //直到 i = j时结束第一大循环 { while(first < last && a[last] >= key) //当i
用它可以处理前多少大的数据提取问题
转载地址:https://islet.blog.csdn.net/article/details/75443720 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!