c - 在 C 中实现降序快速排序

Question

我需要在 C 中实现快速排序(按降序排列)，但我遇到了一些麻烦 - 尤其是在逻辑方面。我正在尝试修改我从 C++ 中的升序快速排序实现中获得的一些旧代码。代码似乎总是准确地返回输入，那么逻辑错误在哪里？

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

#define MAX_SIZE 4

int Array[MAX_SIZE];

void swap(int one, int two) {
    int temp = Array[one];
    Array[one] = Array[two];
    Array[two] = temp;
}

int partition(int left, int right, int pivot) {
    int leftPointer = left - 1;
    int rightPointer = right;
    while (Array[++leftPointer] < pivot) {
    }
    while (rightPointer > 0 && Array[--rightPointer] < pivot) {
        if (leftPointer >= rightPointer) {
            break;
        } else {
            swap(leftPointer, rightPointer);
            swap(leftPointer, right);
        }
    }
    return leftPointer;
}

void Quicksort(int left, int right) {
    if (right - left <= 0) {
        return 0;
    } else {
        int pivot = Array[right];
        int PartitionPoint = partition(left, right, pivot);
        Quicksort(left, PartitionPoint - 1);
        Quicksort(PartitionPoint + 1, right);
    }
}

int main() {
    int i;
    printf("\nGive values");
    for (i = 0; i <= 3; i++) {
        scanf("%d", &Array[i]);
    }
    Quicksort(0, MAX_SIZE - 1);
    printf("\nOutput: ");
    for (i = 0; i <= 3; i++) {
        printf("%d  ", Array[i]);
    }
    return 0;
}

Answer 1

您的代码中存在多个问题:

• partition 函数应该迭代直到 leftPointer 变得大于 rightPointer。
• 第一个 while 循环应该跳过较大的元素，而不是较小的元素。
• 交换 right 元素应该移动到 partition 函数的末尾。
• 由于 partition 假定枢轴位于 right 索引处，因此最好不要将枢轴值作为参数传递。
• Quicksort() 不应返回值。
• 为避免全局变量，数组 Array 应在 main 中本地定义并作为参数传递给函数。

这是一个更正后的版本，可以选择在命令行上接受参数值:

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

void swap(int Array[], int one, int two) {
    int temp = Array[one];
    Array[one] = Array[two];
    Array[two] = temp;
}

int partition(int Array[], int left, int right) {
    int pivot = Array[right];
    int leftPointer = left - 1;
    int rightPointer = right;
    for (;;) {
        while (Array[++leftPointer] > pivot) {
        }
        while (rightPointer > 0 && Array[--rightPointer] < pivot) {
        }
        if (leftPointer >= rightPointer) {
            break;
        } else {
            swap(Array, leftPointer, rightPointer);
        }
    }
    /* move pivot to partition point */
    swap(Array, leftPointer, right);
    return leftPointer;
}

void Quicksort(int Array[], int left, int right) {
    if (left < right) {
        int PartitionPoint = partition(Array, left, right);
        Quicksort(Array, left, PartitionPoint - 1);
        Quicksort(Array, PartitionPoint + 1, right);
    }
}

#define MAX_SIZE 100

int main(int argc, char **argv) {
    int i, n;
    int Array[MAX_SIZE];

    if (argc > 1) {
        for (n = 0; n < MAX_SIZE && n < argc - 1; n++) {
            Array[n] = strtol(argv[n + 1], NULL, 0);
        }
    } else {
        printf("Give values: ");
        for (n = 0; n < MAX_SIZE; n++) {
            if (scanf("%d", &Array[n]) != 1)
                break;
        }
    }

    Quicksort(Array, 0, n - 1);
    printf("\nOutput: ");
    for (i = 0; i < n; i++) {
        printf("%d  ", Array[i]);
    }
    printf("\n");
    return 0;
}