c - 快速排序数组随机数生成器没有打印任何错误

Question

我有这个 C 代码，它创建一个包含 100 个随机数的数组，我想使用快速排序对其进行排序，但它总是给出段错误错误。

这是代码:

#define MAX 100
int a[MAX];
void quick_sort(double *x, int l, int r) {       
    int l1, r1;

    if (l < r) {       
        l1 = l;
        r1 = r;

        do {       
            while (l1 < r && x[l1 - 1] <= x[l - 1]) {       
                l1++;
            }
            while (l < r1 && x[r1 - 1] >= x[l - 1]) {       
                r1--;
            }
            if (l1 < r1) {       
                swap(&x[l1 - l], &x[r1 - 1]);
            }
        } while (l1 < r1);

        swap(&x[l - 1], &x[r1 - 1]);
        quick_sort(x, l, r1 - 1);
        quick_sort(x, r1 + 1, r);
    }
}

void printArray(int a[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", a[i]);
    printf("\n");
}

int main() {
    int i = 1;
    int a_size = sizeof(a) / sizeof(a[0]);
    srand((unsigned int)time(NULL));
    for (i = 0; i < MAX; i++) {
        a[i] = rand() % 501;
    }
    quick_sort(a, 0, a_size);
    printArray(a, a_size);
}

错误是当我运行程序时没有打印任何内容。有人可以帮我解决这个问题吗？

Answer 1

您的代码中有很多问题:

• 您不包括 <stdio.h> , <stdlib.h> ，也不是<time.h> .
• 您的quick_sort函数需要一个指向 double 数组的指针，但你传递了一个 int 数组.
• 函数代码swap()未发布。

• 您在函数 quick_sort 中实现的快速排序算法有缺陷:

  • 您不应扫描 1 大小的切片，使用(r - l > 1) .
  • 您不能使用x[l - 1]作为枢轴，它甚至不是要排序的切片的一部分。此外，您应该在交换阶段之前从数组中提取枢轴，因为它可能会移动。
  • 您不应命名变量 l ，它看起来太接近 1你确实在这里犯了错误:swap(&x[l1 - l], &x[r1 - 1]);
  • 您应该初始化l1和r1这样您就不需要减去 1在很多地方，它会导致困惑和错误的代码。
  • 研究 Wikipedia article 中的算法并将 1 翻译为 C。

这是更正后的版本:

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

#define MAX 100

void swap(int *a, int *b) {
    int x = *a;
    *a = *b;
    *b = x;
}

// Quick Sort using Hoare's original partition scheme
void quick_sort(int *x, int l, int r) {
    if (l < r) {
        int pivot = x[l];
        int l1 = l - 1;
        int r1 = r;

        for (;;) {
            while (x[++l1] < pivot)
                continue;

            while (x[--r1] > pivot)
                continue;

            if (l1 < r1) {
                swap(&x[l1], &x[r1]);
            } else {
                break;
            }
        }
        quick_sort(x, l, r1 + 1);
        quick_sort(x, r1 + 1, r);
    }
}

void printArray(int a[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(void) {
    int a[MAX];
    int a_size = sizeof(a) / sizeof(a[0]);

    srand((unsigned int)time(NULL));

    for (int i = 0; i < MAX; i++) {
        a[i] = rand() % 501;
    }
    quick_sort(a, 0, a_size);

    printArray(a, a_size);
    return 0;
}