QuickSort 实现不适用于重复键

Question

我尝试实现快速排序。它工作正常，除非有一个重复的键，在这种情况下有一个无限循环并且它永远不会终止。你能帮我理解我做错了什么吗？

// quick sort
void quickSort(int arr[], const unsigned size)
{
    // base case
    if (size < 2)
        return;

    int pivot = arr[size / 2];
    unsigned L = 0, U = size - 1;

    // partitioning
    while (L < U) {
        while (arr[L] < pivot)
            L++;
        while (arr[U] > pivot)
            U--;

        swap(&arr[L], &arr[U]);
    }

    quickSort(arr, L); // sort left array
    quickSort(&arr[U + 1], size - L - 1); // sort right array
}

Answer 1

您有小于和大于条件。但是=没有条件。这就是为什么它会运行无限循环的原因。将它们更改为 <= 和 >=.

QuickSort 实现不适用于重复键

QuickSort implementation does not work for duplicate key

c

quicksort