快速排序数组随机数生成器 Nothing Printed Error

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 中的算法并将其中一个翻译成 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;
}

快速排序数组随机数生成器 Nothing Printed Error

Quick Sort Array Random Number Generator Nothing Printed Error

c

arrays

sorting

quicksort