c - 当我在 Quicksort5 函数中激活该行时，它的排序效果不佳。但为什么？

Question

最近在研究快速排序，

我编写了 2 个程序:一个成功运行，而另一个则失败。

我试图找出为什么另一个不起作用。(我知道原因，但我想知道原因下的原因)

两个程序之间的唯一区别是 Quicksort5 函数中的一行，如下:

swap( &list[ ( (backwards-forwards) /2 ) ], &list[last]  );

它们都包含 stdio.h，并且还有 3 个函数，分别称为 main、quicksort5、swap。

程序的上面几行如下:

#include <stdio.h>
int quicksort5(int *, int, int);
int swap(int *, int *);

1)主要功能如下:

int main()
{
    int arrayofintegers[4096];
    int n=0, quantity=0;

    printf("Please enter how many integer numbers you want to get sorted: ");
    scanf("%d",&quantity);

    if (quantity <= 0)
        return -1;

    printf("\nPlease give at max 10 digits per number.\n\n");
    while ( n<quantity ) //import the numbers
    {
        printf("the     %5d. number = ",n+1);
        scanf("%d",&arrayofintegers[n]);
        n++;
    }
    printf("\n");

    quicksort5(arrayofintegers, 0, quantity-1);

    n=0;
    while ( n<quantity ) //The numbers will be displayed.
    {
        printf("the new %5d. number =%11d\n", n+1, arrayofintegers[n]);
        n++;
    }

    return 0;
}

2)quicksort5函数如下:

int quicksort5(int *list, int forwards, int backwards)
{
    if ( forwards >= backwards )
        return 0;

    int const first   = forwards;
    int const last    = backwards;

    /* //If I make the line bellow active the function doesn't sort successfully. But I want to know the main reason in this.
    swap( &list[ ( (backwards-forwards) /2 ) ], &list[last]  ); */

    int const pivot = list[last];

    int isforwardswaiting  = 0;
    int isbackwardswaiting = 0;


    backwards--; // the pivot won't change
    while (forwards<backwards)
    {
        isforwardswaiting   = (list[forwards]  >= pivot);
        isbackwardswaiting  = (list[backwards] <  pivot);

        if(isforwardswaiting && isbackwardswaiting)
        {
            swap(&list[forwards],&list[backwards]);
            forwards++;
            backwards--;
        }
        else
        {
            if ( !(isforwardswaiting))
                forwards++;

            if ( !(isbackwardswaiting))
                backwards--;
        }
    }

    if (list[forwards] < pivot)
        forwards++;

    swap(&list[forwards],&list[last]); //placing the pivot

    /* list[first], list[first+1] ... list[forwards-2], list[forwards-1] ==> the numbers smaller than the pivot
       list[forwards]                                                    ==> the number which is the pivot
       list[forwards+1], list[forwards+2] ... list[last-1], list[last]   ==> the numbers greater than the pivot */

    quicksort5(list, first, forwards-1);
    quicksort5(list, forwards+1, last);
}

3)交换函数如下:

int swap(int *a, int *b)
{
    int c=*a;
    *a=*b;
    *b=c;
    return 0;
}

预先感谢您的回答。

Answer 1

您只需修改函数 Quicksort5 中的以下行:

swap( &list[ ( (向后-向前)/2 ) ], &list[最后] );

对此:

swap( &list[ (向前 + (向后-向前)/2 ) ], &list[最后] );

要理解为什么第一个语句会导致问题，请考虑 backwards = 6 和 forwards = 4 时的情况。因此，(backwards-forwards)/2 的计算结果为 1，并且交换函数将索引 6 处的元素与索引 1 处的元素交换，这是不希望的。

希望对你有帮助!