0

我编写了快速排序算法的以下实现。我无法猜测为什么以下代码片段不起作用（编译良好但无法在运行时运行 a.exe 已停止工作）。如果你们中的任何人可以提供帮助，我将很高兴我在这方面：

main( )
{
    int a[ ]={9,2,3,1,6,5,6,3,2,9,8,1,4,5,5,6,5,99};
    quicksort(a,0,17);
    print(a,18);

}

void print(int a[ ],int n)
{
int i;
for (i=0;i<n;i++)
        printf("%d\n",a[i]);
} 

   void swap(int a[ ],int left,int right)
      {
        int t;
        t=a[left];
            a[left]=a[right];
            a[right]=t;
     }

   void quicksort(int a[ ],int left,int right)
   {
    int i,last;
        if ( left >= right)
            return;
    swap(a,left,(last+right)/2);
        last=left;
        for (i=last+1;i<=right;i++)
            if (a[i] < a[left])
                swap(a,++last,i);
        swap(a,left,last);
        quicksort(a,left,last-1);
        quicksort(a,last+1,right);

}

4

3 回答 3

0

这段代码中有两个问题。一个是一般的编码规则，每个变量都应该用一个值初始化，否则你的变量可能会采用垃圾值并给出意外的输出。第二个是你的算法有问题。在调用交换函数的函数快速排序中，要传递的正确参数是“swap(a,left,( left +right)/2);”

PS - 如果在项目上工作，也请提供函数原型，否则忽略这一点。

于 2013-06-19T06:01:47.290 回答
0

问题就在这里：

void quicksort(int a[ ],int left,int right)
{
    int i,last;
    if ( left >= right)
        return;
    swap(a,left,(last+right)/2);
                 ^^^^

last未初始化，但您将其用作right.

你的意思是(left+right)/2？

我的编译器不仅警告我（总是启用警告），而且我进一步使用调试器仔细检查确实是这样。

编译器警告：

23:22: warning: ‘last’ may be used uninitialized in this function [-Wuninitialized]

调试器输出：

Breakpoint 2, main () at quicksortbroken.c:37
37      int a[ ]={9,2,3,1,6,5,6,3,2,9,8,1,4,5,5,6,5,99};
(gdb) n // go to the next line
38      quicksort(a, 0, 17);
(gdb) s // step into the function
quicksort (a=0xbffff6d8, left=0, right=17) at quicksortbroken.c:21
21      if ( left >= right)
(gdb) n 
23      swap(a,left,(last+right)/2); // okay, let's examine the variable I suspect is problematic
(gdb) p last // print the value of last
$1 = 1872329 // Oh, oh, definitely not supposed to be this value

这是在 Linux 下使用 GDB，不确定您是如何编译代码的，但我很确定 Cygwin 带有 GDB 的 Windows 端口，Microsoft 也有自己的调试器。没有借口不使用一个。

于 2013-06-19T05:21:13.413 回答
0

也许你错过了一个警告，比如 ‘last’ may be used uninitialized in this function

在没有初始化的情况下首次使用last会产生分段错误，因此您的 exe 无法按预期工作。

于 2013-06-19T05:25:05.200 回答