快速排序主元的特殊情况

Question

我在 C 中实现了快速排序，运行非常好。然后我开始玩枢轴元素，现在我陷入了一个奇怪的境地。我实施的运行有时很好，但在其他所有时间都没有运行（显示无输出），我无法查明为什么会发生这种情况。这是我的代码。

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


void swap(int *x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void displayArray(int arr[], size_t size)
{
    for(int i = 0; i < size; ++i)
        printf("%d\t",arr[i]);
    printf("\n");
}

unsigned int getNMinNMax(int arr[], unsigned int lb, unsigned int ub)
{
    unsigned int a = rand()%(ub-lb +1) + lb, b =rand()%(ub-lb +1) + lb,c = rand()%(ub-lb +1) + lb;
    // printf("%d %d %d \n", a,b,c);
    // getchar();
    // inefficient comparisons incoming, brace yourselves
    if(arr[a] >= arr[b] && arr[a] < arr[c]) return a;
    else if(arr[b] >= arr[a] && arr[b] < arr[c]) return b;
    else return c;
}

unsigned int partition(int arr[], unsigned int lb, unsigned int ub)
{
    // pivot selection mania(select necessarily from array elements)****{needs more testing}
    // 1)middle element
    // swap(&arr[lb + (ub - lb)/2], &arr[lb]);
    // 2)neither smallest nor largest
    // swap(&arr[getNMinNMax(arr,lb,ub)], &arr[lb]); (problem here)
    // 3)random
    // swap(&arr[rand()%(ub-lb +1) + lb], &arr[lb]); (problem here)
    // 4)1st element(no optimisation)
    int pivot = arr[lb];
    unsigned int down = lb + 1, up = ub;
    while(down <= up)
    {
        while(arr[down] <= pivot)
            down++;
        while(arr[up] > pivot)
            up--;
        if(down < up)
            swap(&arr[down], &arr[up]);
    }
    arr[lb] = arr[up];
    arr[up] = pivot;
    return up;
}

void quickSort(int arr[], unsigned int lb, unsigned int ub)
{
    while(lb < ub)
    {
        unsigned int pivot = partition(arr, lb, ub);
        if (pivot - lb < ub - pivot)
        {
            quickSort(arr, lb, pivot - 1);
            lb = pivot + 1;
        }
        else
        {
            quickSort(arr, pivot + 1, ub);
            ub = pivot - 1;
        }
    }
}

int main()
{
    int arr[] = {1,2,3,5,0,-1,-2,-3};
    srand(time(NULL));
    quickSort(arr, 0, sizeof(arr)/sizeof(int)-1);
    displayArray(arr,sizeof(arr)/sizeof(int));
    return 0;
}

我已经评论了哪些行导致输出消失。我很确定我的实现在其他情况下有效，因为我没有遇到那些输出消失的问题，但请随时指出任何其他错误。我使用的编译器是Onlinegdb C编译器（即gcc afaik）。

PS：我已经添加了我的完整代码，因为我发现当我弄乱我的分区函数时我的显示函数不起作用很奇怪。我也试过调试，但没有成功。

Answer 1

问题是由于：

while(lb < ub)

调整主元后，ub可以达到-1，但是ub的类型是unsigned int，所以ub看起来是一个很大的正数，while循环会继续。

将此行更改为：

while( (int)lb < (int)ub )

允许程序完成并显示排序后的数组。

快速排序主元的特殊情况

A peculiar case of quicksort pivot

c

sorting

algorithm

quicksort