这是一个快速排序的算法，基本情况是对的，有特殊情况没考虑到，有大哥能帮忙吗？

Question

#include
#include
#define SWAP(x,y) {int t;t=x;x=y;y=t;}

void quicksort(int a[],int left,int right) {
//数组最左边的那个数为基数
int i,j,s;
s=a[left];
if(left while(1) {
for(i=left+1; i if(a[i]>=s) break;
}//从左往右找到第一个大于等于基数的数
for(j=right; j>=left+1; j--) {
if(a[j] }//从右往左找到第一个小于基数的数
if(i>=j) break;
/*i>=j表示右边已经都是大于基数的数，
左边都是小于基数的数*/
SWAP(a[i],a[j]);
}
SWAP(a[left],a[j]);
quicksort(a,left,j-1);
quicksort(a,j+1,right);
}
}

int main() {
int t;//t组数据
scanf("%d",&t);
while(t--) {
int i,n;
int a[100005];
scanf("%d",&n);//每组数据的大小
for(i=0; i<n; i++) {
scanf("%d",&a[i]);
}
quicksort(a,0,n-1);
int flag=0;
for(i=0; i<n; i++) {//输出排完序后的数据
if(flag) printf(" ");
printf("%d",a[i]);
flag++;
}
printf("\n");
}
return 0;
}

Answer 1

我觉得是你在把轴值放回去的操作出了问题，我讲快排写了三个函数，请您看一下是否有帮助

 int findpivot(int a[], int i, int j)
{
    //return (i + j) / 2;
        return rand()%(j-i)+i; //随机给出轴值 
}
int partition(int *a, int l, int r, int& pivot)
{
    do {
        while (a[++l]>pivot);//左面找到小于轴值的 
        while ((l<r) && (a[--r]<pivot));//右面找到大于轴值的 
        swap(a[l], a[r]);//将二者交换 
    } while (l<r);
    return l;//返回比轴值小的第一个数的位置 
}
void qsort(int *A, int i, int j) {
    if (j <= i)return;
    int pivotindex = findpivot(A, i, j);//随机产生一个轴 
    swap(A, pivotindex, j);//将轴值放到尾部 
    int k = partition(A, i - 1, j, A[j]);//k为划分后的右半部分的起始位置 
    swap(A, k, j); //将轴值放回去 
    qsort(A, i, k - 1);//递归 左 
    qsort(A, k + 1, j); //递归 右 
}