快速排序跳过一个元素

Question

所以今天我试图实施一种快速分类。它几乎可以正常工作，但是以某种方式跳过了一个元素。

example : 5 2 8 2 3 4 1 5 7 -5 -1 -9 2 4 5 7 6 1 4

output : -5 -1 -9 1 2 2 3 2 1 4 4 4 5 5 5 6 7 7 8

在这种情况下，它会跳过-9。这是函数的代码。

test = quicksort_asc(0,size,tab,size) // this is function call 

int quicksort_asc(int l, int r, int tab[], int tabSize) //l is first index, r is last index, tabSize is tabsize-1 generally
{
    int i,buffer,lim,pivot,flag=0;
    if(l == r)
        return 0;

    lim = l-1;
    pivot = tab[r-1];
    printf("pivot:%d\n",pivot);
    for (i = l; i <= r-1; ++i)
    {
        if(tab[i] < pivot) {
            lim++;
            buffer = tab[lim];
            tab[lim] = tab[i];
            tab[i] = buffer;
            flag = 1;
        }
    }
    if(flag == 0)
        return 0;
    buffer = tab[lim+1];
    tab[lim+1] = pivot;
    tab[r-1] = buffer;
    quicksort_asc(l,lim+1,tab,lim+1);//left side
    quicksort_asc(lim+1,tabSize,tab,tabSize);//right side

}

这是我的数组长度计数代码。 100是最大大小，0是停止值。数量就是大小。

 int count=0;
    for (int i = 0; i < 100; i++)
    {
        test = scanf("%d",&vec[i]);
        if(vec[i] == 0) break;
        count++;
    }
    return count;

Answer 1

似乎没有人急于帮助您。：）

对于初学者，最后一个参数是多余的。

int quicksort_asc(int l, int r, int tab[], int tabSize);
                                           ^^^^^^^^^^^

您需要的是指向数组第一个元素以及起始索引和结束索引的指针。

也可以使用索引类型int代替索引的类型size_t。但是，当您使用表达式语句时

lim = l-1;

然后让索引将具有int类型，尽管您可以在没有此表达式语句的情况下使用另一种方法。

因此该函数应声明为

void quicksort_asc( int tab[], int l, int r );

变量flag是冗余的。当它等于0时，表示枢轴值之前的所有元素都大于它。但是，尽管如此，您必须将枢轴值与大于或等于枢轴的第一个元素交换。

此循环

for (i = l; i <= r-1; ++i)

具有一个迭代冗余。应该设置为

for (i = l; i < r-1; ++i)

此电话

quicksort_asc(lim+1,tabSize,tab,tabSize);
              ^^^^^

应代替此电话

quicksort_asc( lim + 2, tabSize,tab );

因为该子数组中不包含枢轴值。

这里是演示程序。

#include <stdio.h>

void quicksort_asc( int tab[], int l, int r )
{
    if ( l != r )
    {
        int lim = l - 1;

        int pivot = tab[r - 1];

        for ( int i = l; i < r - 1; ++i )
        {
            if ( tab[i] < pivot ) 
            {
                lim++;

                int tmp = tab[lim];
                tab[lim] = tab[i];
                tab[i] = tmp;
            }
        }

        tab[r - 1] = tab[lim + 1];
        tab[lim + 1] = pivot;
        quicksort_asc( tab, l, lim + 1 );
        quicksort_asc( tab, lim + 2, r );
    }       
}

int main(void)
{
    int a[] = { 5, 2, 8, 2, 3, 4, 1, 5, 7, -5, -1, -9, 2, 4, 5, 7, 6, 1, 4 };
    const int N = ( int )( sizeof( a ) / sizeof( *a ) );

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

    quicksort_asc( a, 0, N );

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

    return 0;
}

其输出为

5 2 8 2 3 4 1 5 7 -5 -1 -9 2 4 5 7 6 1 4 
-9 -5 -1 1 1 2 2 2 3 4 4 4 5 5 5 6 7 7 8