Question

求大神帮我看一看这个快速排序C++程序拉你出错了，谢谢！vs没报错，但一运行就中断，

#include<iostream>
using namespace std;
int Partition(int* A,int p,int r)
{
int x,i,j;
x=A[p];
i=p;
for(j=p+1;j<=r;j++)
{
if(A[j]<=x) {
i=i+1;
swap (A[i],A[j]);
}
}
swap (A[p],A[i]);
return i;
}
void Quick_sort(int* A,int p,int r)
{
int q;
if(p<r){
q=Partition(A,p,r);
Quick_sort(A,p,q-1);
Quick_sort(A,q+1,r);
}
}
void swap(int*x,int*y)
{
int t;
t=*x;
*x=*y;
*y=t;
}
int main()
{
int m,n,o;
int* S=new int[n];
cout<<"Please input the Sequence length:\n";
cin>>n;
cout<<"Please input the number sequence:\n";
for(m=1;m<=n;m++)
{
cin>> o;
S[m]=o;
}
Quick_sort(S,m,n);
for(m=1;m<=n;m++)
{
cout<<S[m];
}
cout<<endl;
}

Answer 1

兰州 你的n没有初始化啊...你咋么知道new的大小？！ 一开始出错就是这个问题 还有问题请继续

兰州 基本上十把你的代码QuickSort函数全改了... 实测 通过... 有注释 望采纳....
.
void QuickSort(int a[],int low,int high)
//对元素a[low]~a[high]进行快排
{
int i=low,j=high;
int temp =a[low];
while(i<j)//循环控制条件
{
while(i<j && temp<=a[j]) j--;//在数组右端扫描
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j && a[i]<temp ) i++;//在素组左端扫描
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
if(low<i) QuickSort(a,low,i-1);
if(i<high) QuickSort(a,j+1,high);
}
int main()
{
int m,n=100,o; //直接复制n比较大的一个数- - 怕你直接来个99...
int* S=new int[n];
cout<<"Please input the Sequence length:\n";
cin>>n;
cout<<"Please input the number sequence:\n";
for(m=0;m<n;m++) //一般数组下标是从0开始的 兰州下次要注意 你的代码数组会越界的
{
cin>> o;
S[m]=o; //其实我觉得o变量完全没有必要 直接cin>>S[m]就行了
}
QuickSort(S,0,n-1); //快排
for(m=0;m<n;m++) //输出
{
cout<<S[m]<<" " ;
}
cout<<endl;
}

追问

我按你说的另n=100修改我自己写的那个代码，可以运行，但是为什么输入一下数据之后它没有排序直接按照原来数据输出，请问是怎么回事呢？

追答

首先回答是为什么你 数据直接按原来输出 是因为在main()函数中中 for(m=0;m<n;m++)  m等于n了 所以你调用QuickSort函数时没效果 因为根本没有运行

然后我根据你的思路在你代码基础上更改了写 发现你的Partition()函数其实做的相当于每次快排的事情 所以没必要返回位置了              只要循环调用即可  下面是更改后的代码 实测通过 

#include<iostream>

using namespace std;

int Partition(int* A,int p,int r)

//兰州你这个函数是获取A[p]经过一次快排后的下标吧 并且把小于A[p]的数放到前面去...

{

int x,i,j;

x=A[p];

i=p;

//for(j=p+1;j<=r;j++)        //由于更改后的main()函数从0开始的 j=r时会越界

for(j=p+1;j<r;j++)

{ 

if(A[j]<=x) {

i=i+1;

swap (A[i],A[j]);

}

}

swap (A[p],A[i]);

return i;

}

void Quick_sort(int* A,int p,int r)

{   

//int q;

//q=Partition(A,p,r);

//if(p<q-1)         //问题  Quick_sort(A,p,q-1);

//if(q+1<r)

//Quick_sort(A,q+1,r);

for(int i=p;i<r;i++)

Partition( A,i,r);

}

void swap(int*x,int*y) 

{

int t;

t=*x;

*x=*y;

*y=t;

}

int main()

{

int m,n,o;                  //n没初始化 导致下面new出错 你可以先输入n再new

cout<<"Please input the Sequence length:\n";

cin>>n;

int* S=new int[n];

cout<<"Please input the number sequence:\n";

//for(m=1;m<=n;m++)               //建议每次都从0开始 如果m==n这 数组会越界的 

for(m=0;m<n;m++) 

{

cin>> o;

S[m]=o;

}

//Quick_sort(S,m,n);               //这个调用有点不懂...这个时候m与n相等的啊   

Quick_sort(S,0,n);                // 排序从小标为0 的开始

for(m=0;m<n;m++)

{

cout<<S[m]<<" ";

}

cout<<endl;

}

兰州你还是把我单独写的QuickSort函数看看....那个是按照快排的步骤来写的

还有什么问题直接问

追问

真的非常感谢你，我总算搞懂了，最近自学C++，所以一些细节还不是很清楚，万分感谢~分给你了。

Answer 2

#include<iostream>using namespace std;
int Partition(int* A,int p,int r)
{
int x,i,j;
x=A[p];
i=p;
for(j=p+1;j<=r;j++)
{
if(A[j]<=x) {
i=i+1;
swap (A[i],A[j]);
}
}
swap (A[p],A[i]);
return i;
}
void Quick_sort(int* A,int p,int r)
{
int q;
q=Partition(A,p,r);

if(p<q-1) //问题 Quick_sort(A,p,q-1);
if(q+1<r)
Quick_sort(A,q+1,r);

}void swap(int*x,int*y)
{
int t;
t=*x;
*x=*y;
*y=t;
}
int main()
{
int m,n,o;
int* S=new int[n];
cout<<"Please input the Sequence length:\n";
cin>>n;
cout<<"Please input the number sequence:\n";
for(m=1;m<=n;m++)
{
cin>> o;
S[m]=o;
}
Quick_sort(S,m,n);
for(m=1;m<=n;m++)
{
cout<<S[m];
}
cout<<endl;
}