1、环境配置：
- 系统：win10
- 编程语言：C++
- 编译器：DevC++
2、算法思想：
- 以数组中第一个元素为标准，让比它大的去它右边，让比他小的去它左边，然后在他右边实行同样的方法，在他左边实行同样的方法；
- 伪代码
int fast( i, j, a[1 ... n] )//i为a[]的首项下标，j为a[]的最后一项下标
{
if ( i >= j ) then return(0);
bz = a[i]; //选第一个作为标准
p = i; //p是指向标准的指针
z = j;
for m = i to m < z+1 do
{
if ( bz > a[m] ) then {
sl = a[m];
a[m] = a[p];
a[p] = sl;
p = m;
}
if ( bz < a[m] ) then { //比bz大的直接放到最后一个
sh = a[m];
a[m] = a[z];
a[z] = sh;
z = z - 1;
m = m - 1;
}
}
fast( p + 1, j, a );
fast( i, p - 1, a );
}
3、第一代代码：
- 实现了把大的放右边，小的放左边的操作。
/*
《快速排序》
1、取一个数组中的第一位数i，然后比较其余数，
重排，让i的左边比i小，右边比i大。
2、然后从左边取第一个数重复上述过程，右边取
第一个数，重复上述过程。
3、终止条件是左右两边都只剩一个数据
*/
#include<iostream>
using namespace std;
int fast(int i,int j,int a[]);//i是开始序号，j是结束序号。
int main()
{
int A[] = {4,2,5,3,6,0};
for(int s=0; s<sizeof(A)/sizeof(A[0]); s++){
cout<<A[s]<<",";
}
cout<<""<<endl;
for(int tm=0; tm<sizeof(A)/sizeof(A[0]); tm++){
cout<<"_____";
}
cout<<""<<endl;
fast(0,5,A);
cout<<""<<endl;
for(int tm=0; tm<sizeof(A)/sizeof(A[0]); tm++){
cout<<"_____";
}
cout<<""<<endl;
for(int s=0; s<sizeof(A)/sizeof(A[0]); s++){
cout<<A[s]<<",";
}
return 0;
}
//快速排序
int fast(int i,int j,int a[]){
if(i == j){
return 0;
}
int bz = a[i];//选第一个作为标准
int p = i;//p是指向标准的指针
int z = j;
for(int m=i; m<z+1; m++){
cout<<"m= "<<m<<" |";
if(bz > a[m]){
int sl=0;
sl = a[m];
a[m] = a[p];
a[p] = sl;
p = m;
}
if(bz < a[m]){
if(m == z){
return 0;
}
int sh=0;
sh = a[m];
a[m] = a[z];
a[z] = sh;
z=z-1;
m=m-1;
}
for(int s=0; s<j+1; s++){
cout<<a[s]<<",";
}
cout<<"i="<<i<<" j="<<j<<endl;
cout<<""<<endl;
}
}
4、结果展示：
结果展示.png
关于第一代代码反思分析：
- 问题一：第一代代码是可以实现“左小右大”的第一次筛选了，但是发现在完成筛选循环后，在fast代码最后最后添加fast(p+1,j,a);和fast(i,p-1,a);这两条代码就是不执行，原因如下：
//程序有两个出口
if(i == j){
return 0;
}
...
if(bz < a[m])//本意是在调整右边的时候，不用遍历完所有数组元素就能早点结束。
{
if(m == z){
return 0;
}
测试后发现，去掉第二个出口，对程序结果没有影响，程序只不过会遍历完所有数组元素而已。
- 问题二：在调整了出口问题后，我发现，在fast代码最后最后添加fast(i,p-1,a)，程序可以跑，可以将左边部分顺利排序，但是在添加fast(p+1,j,a);程序就会出错。原来是p在fast代码中随着m的增加有可能增加，然后在传递的时候，会通过p+1继续增加一次。这样的话，原来的递归终止条件if(i == j)就会无法响应，程序会陷入死循环，这个在下面的代码中有注释。
- 总结：第一代代码在解决了上述两个问题之后，就能实现递归调用了！
5、第二代代码：
- 将整个数组排序。
#include<iostream>
using namespace std;
int fast(int i,int j,int a[]);//i是开始序号，j是结束序号。
int main()
{
int A[] = {4,2,5,3,6,0};
for(int s=0; s<sizeof(A)/sizeof(A[0]); s++){
cout<<A[s]<<",";
}
cout<<""<<endl;
for(int tm=0; tm<sizeof(A)/sizeof(A[0]); tm++){
cout<<"_____";
}
cout<<""<<endl;
fast(0,5,A);
cout<<""<<endl;
for(int tm=0; tm<sizeof(A)/sizeof(A[0]); tm++){
cout<<"_____";
}
cout<<""<<endl;
for(int s=0; s<sizeof(A)/sizeof(A[0]); s++){
cout<<A[s]<<",";
}
return 0;
}
//快速排序
int fast(int i,int j,int a[]){
/*
这里如果设置成i==j，在判断左边的时候，不会出错。
在判断右边的时候，p有可能在程序中向右移动一次，
然后在传参时继续移动一次，导致p>j，陷入死循环。
*/
if(i >= j)
{
return 0;
}
int bz = a[i];//选第一个作为标准
int p = i;//p是指向标准的指针
int z = j;
for(int m=i; m<z+1; m++){
if(bz > a[m]){
int sl=0;
sl = a[m];
a[m] = a[p];
a[p] = sl;
p = m;//在这里p会向后移动
}
if(bz < a[m]){
int sh=0;
sh = a[m];
a[m] = a[z];
a[z] = sh;
z=z-1;
m=m-1;
}
}
/*
发现使用递归排左边没问题，排右边就陷入死循环，
下面两条打印语句帮了大忙，DEVC++缺点就是排错太难了。
*/
cout<<"i="<<i<<",j="<<j<<endl;
cout<<"p="<<p<<endl;
fast(p+1,j,a);
fast(i,p-1,a);
}
6、结果展示：
结果展示.png
7、反思总结：
- 1、写递归程序的时候，一定要注意出口（递归终止条件/递归返回条件）设置过多，可能会造成无法递归执行。
- 2、写递归程序之前一定要把算法思路明确，然后先实现算法思路当中的“基本任务”，比如这个算法中基本任务就是选第一个做标准，小的放它左边，大的放它右边。完成了基本任务，调整调整程序，加上“自己调自己”这个步骤，就能实现递归了。
网友评论