c - 为什么我在运行我的快速排序算法代码时收到 fastsort.exe 已停止工作并出现错误 255 <0xff>？我正在使用代码块

Question

我在代码块上运行此代码并收到错误，因为 quicksort.exe 已停止工作。主要功能运行良好。是什么原因？我该如何解决这个问题？

代码如下:

#include <stdio.h>
#include <stdlib.h>

void quicksort(int *,int,int);
int part(int *,int,int);

int main()
{
    int i,n, a[100];
    printf("Enter the length of array\n");
    scanf("%d",&n);
    printf("Enter array elements\n");

    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    quicksort(a,0,n-1);
    printf("\nSorted array:\n");

    for(i=0;i<n;i++)
        printf("%d\n",a[i]);

    return 0;
}


void quicksort(int *a,int lb,int ub)
{
    int p;

    if(lb>ub)
        return;

    p= part(a,lb,ub);
    quicksort(a,lb,p-1);
    quicksort(a,p+1,ub);
    return;
 }

int part(int *x, int l, int u)
{

    int piv,i,t,t2,pos=l;
    piv=x[u];

    for(i=l;i<=u;i++)
    {
        if(x[i]<=piv)
        {
            t=x[i];
            x[i]=x[pos];
            x[pos]=t;
            pos++;
        }

    }
    t2=x[pos];
    x[pos]=x[u];
    x[u]=t2;
    return pos;
}

虽然所有其他排序算法都工作正常。我在合并排序和快速排序中遇到问题。

问题出在递归还是指针上？

Answer 1

你可以这样修改你的代码(有两个代码最接近你的想法，我添加注释):

#include <stdio.h>
#include <stdlib.h>

void quicksort(int *,int,int);
int part(int *,int,int);

int main()
{
    int i,n, a[100];
    printf("Enter the length of array\n");
    scanf("%d",&n);
    printf("Enter array elements\n");

    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    quicksort(a,0,n-1);
    printf("\nSorted array:\n");

    for(i=0;i<n;i++)
        printf("%d\n",a[i]);

    return 0;
}


void quicksort(int *a,int lb,int ub)
{
    int p;

    if(lb>ub)
        return;

    p= part(a,lb,ub);
    quicksort(a,lb,p-1);
    quicksort(a,p+1,ub);
    return;
}

int part(int *x, int l, int u)
{

    int piv,i,t,pos=l-1;  //not pos = l 
    piv=x[u];

    for(i=l;i<=u;i++) // You can write:for(i = l; i < u; i++)
    {
        if(x[i]<=piv)
        {
            pos++;    //pos should add 1 before swap
            t=x[i];
            x[i]=x[pos];
            x[pos]=t;
        }

    }
    //If you write for(i = l; i < u; i++), use the following three lines of code
    //t2=x[pos+1]; 
    //x[pos+1]=x[u];
    //x[u]=t2;
    return pos;
}

我认为你的代码崩溃的原因是如果你使用 pos = l 并在 swap 之后写入 pos++ ，x[pos] 可能会发生越界了。但是即使修改了，还是有其他错误。也许你应该画一张图来理解快速排序，了解更多细节。