0

我已经实现了一个快速排序算法，但是当我测试它时，我注意到当输入数组在第一个元素中具有最大元素时它会失败（这是我从中获得枢轴的元素）。这是我的代码：

void partition(int *a,int size){
    if(size<=1){return;}
    int pivot=a[0];
    int left=0,right=0;
    for(left=1,right=size-1;left<=right;){    //was size-1
        if(a[left]>=pivot&&a[right]<=pivot) {
            swap(left,right,a);
        }

        if(a[left]<pivot){left++;}
        if(a[right]>pivot){right--;}
    }
    swap(0,right,a);
    partition(a,right-1);
    partition(&(a[right+1]),size-right-1);
}

它失败的一些示例：

I/P 245  111  32    4
O/P 4   111  32  245     `

I/P 154   11   43  3  7
O/P   7   11   43  3  154

我犯了哪些可能的错误？

4

2 回答 2

2

您错过了在分区函数中数组中有一个元素是枢轴的情况。

认为arr = { 5, 5, 1 , 1, 5, } 

pivot = 5
iter1:
left=1, arr[left]=5 ; right=4,arr[right]=5
(swapping)
not increasing left nor decreasing right - since 5 < 5 == false ; 5 > 5 == false

下一次迭代，同样的场景会重演，你实际上会得到一个无限循环。

处理它的一种方法是确定“大”部分还将增加所有恰好是枢轴的元素，如果 (not ) 则交换元素，如果( arr[right] < pivotnot )则<=减少元素，例如：rightarr[right] >= pivot>

...
for(left=1,right=size-1;left<=right;){    //was size-1      
        if(a[left]>=pivot&&a[right]<pivot) { 
        //                         ^ note < not <=
        swap(left,right,a);
    }

    if(a[left]<pivot){left++;}
    if(a[right]>=pivot){right--;}
    //        ^ note >=
}
...
于 2012-12-09T18:41:39.993 回答
2

好吧，问题出在这里：

partition(a,right-1); // <- It's partition(array,size)!

将其更改为

partition(a,right);

它会起作用。我想你知道原因。
要使分区功能正常工作，您必须提供 2 件事：

1）要处理的数组。
2）它具有的元素数量，大小。

问题在于对左子数组进行分区的第一次递归调用：  partition(a,right-1)

参数 2，即 size，被错误地指定为right-1，而实际上它是right。

这可以通过使用数组中从索引a到b（都包括在内b>=a） 的元素数是 的事实来计算N= b-a+1。

在这里，我们有a=0, b=right-1，因此左子数组中的元素数size, N= (right-1)-(0)+1= right。

因此，要正常工作，您必须将其称为partition(a,right);. 左子数组以 结尾right-1，但它有right-1+1=right元素。

一直在发生:)

于 2012-12-09T18:53:16.470 回答