c - QuickSort 排序正整数，有时排序后第一个值是负整数

Question

我正在用 C 实现一个 QuickSort，它的主元是可变的(可以是中间的、中位数的或随机的)。它是在 switch 子句中选择的。

我的实现是:

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

// swap two values
void intercambio(int *arrayDatos, int inicio, int fin) {
    int temporal;

    temporal = arrayDatos[inicio];
    arrayDatos[inicio] = arrayDatos[fin];
    arrayDatos[fin] = temporal;
}

// calculate median
int calcularMediana(int a[], int left, int right) { //Uses median of three partitioning technique
    int center = (left + right) / 2;
    if (a[center] < a[left])
        intercambio(a, left, center);
    if (a[right] < a[left])
        intercambio(a, left, right);
    if (a[right] < a[center])
        intercambio(a, center, right);

    intercambio(a, center, right - 1); //since the largest is already in the right.
    return right - 1;
}

// arrayDatos is array to sorting
// inicio is start of the partition
// fin is end of the partition
// variante is the variable which select the pivote type (0, 1 or 2)
int quickSort(int *arrayDatos, int inicio, int fin, int variante) {
    int pivote, i, j;

    // vector size 1 -> dont do nothing
    if (inicio >= fin)
        return 0;
    // vector size 1 -> check if is necessary swap it
    if (inicio + 1 == fin) {
        if (arrayDatos[inicio] > arrayDatos[fin]) { // No están ordenados los dos números, intercambiar
            intercambio(arrayDatos, inicio, fin);
        }
        return 0;
    }
    // vector size 3+ 
    switch (variante) {
        case 0: // MIDDLE
        {
            int medio = (inicio + fin) / 2;
            // swap pivot and last element
            intercambio(arrayDatos, medio, fin);
            break;
        }
        case 1: //ALEATORY
        {
            int aleatorio = inicio + rand() % (fin - inicio);
            // swap pivot and last element
            intercambio(arrayDatos, aleatorio, fin);
            break;
        }
        case 2: //MEDIAN
        {
            int mediana = calcularMediana(arrayDatos, inicio, fin);
            // swap pivot and last element
            intercambio(arrayDatos, mediana, fin);
            break;
        }
        default:
            printf("No valid pivot. \n");
            break;
    }
    pivote = arrayDatos[fin];
    // start partition
    for (i = inicio, j = fin - 1;;) {
        while ((i <= fin - 1) && (arrayDatos[i] <= pivote)) {
            i++;
        }
        while ((j >= inicio) && (pivote <= arrayDatos[j])) {
            j--;
        }
        if (i < j) { // swap numbers
            intercambio(arrayDatos, i, j);
            i++;
            j--;
        } else // end partition
            break;
    }
    // restore pivot
    intercambio(arrayDatos, i, fin);
    // end partition, recursive calls
    quickSort(arrayDatos, inicio, i - 1, variante); // Vector de la izquierda del pivote
    quickSort(arrayDatos, i + 1, fin, variante); // Vector de la derecha del pivote

    return (0);
}

int main() {
    int *a = malloc(4 * sizeof(int));
    a[0] = 2;
    a[1] = 5;
    a[2] = 4;
    a[3] = 9;

    quickSort(a, 0, 4, 2);

    for (int i = 0; i < 4; ++i) 
        printf("%i \n", a[i]);
}

但有时我在排序后得到一个负数作为第一个元素，而其他时候排序做得很好。

我的意思是(假设 vector :{5, 1, 4})，可能的结果是:

• 有时结果没问题:{1, 4, 5}
• 有时结果不正常:{-124565646, 4, 5}

我已经在代码中寻找可能的错误，但我没有找到任何错误。

知道为什么会这样吗？

Answer 1

关于 fin 处的元素是包含在要排序的数组中还是排除在外，您的代码存在混淆。

函数 quickSort 似乎包含它，但您从 main 调用 quickSort(a, 0, 4, 2); 并使用数组大小为 4，fin 的值为 4，因此包括索引 4 处的元素，这不是部分数组的。

因此，代码具有未定义的行为，输出可能无法预测。访问超出数组末尾的元素可能会导致 fatal error ，或者可能会返回一个您观察到的无意义的值。如果此值恰好为负数，quickSort 会将其移动到数组的开头并在输出中显示它。

在当前的实现中，main 中的调用应该是 quickSort(a, 0, 3, 2);。

然而，在 C 中，fin 是从范围中排除的第一个值的索引会更加一致。这需要对代码进行更多更改。

另请注意，int medio = (inicio + fin)/2; 中可能存在算术溢出。你应该改为写:

    int medio = inicio + (fin - inicio) / 2;

这是您的代码的修改版本，其中包含验证步骤和一些关于比较和交换次数的统计信息:

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

static long long comparisons, exchanges;

// swap two values
void intercambio(int *arrayDatos, int i, int j) {
    int temporal = arrayDatos[i];
    arrayDatos[i] = arrayDatos[j];
    arrayDatos[j] = temporal;
    exchanges++;
}

// calculate median of 3
int calcularMediana(int a[], int left, int right) {
    int center = left + (right - left) / 2;
    comparisons++;
    if (a[center] < a[left])
        intercambio(a, left, center);
    comparisons++;
    if (a[right] < a[left])
        intercambio(a, left, right);
    comparisons++;
    if (a[right] < a[center])
        intercambio(a, center, right);
    return center;
}

// arrayDatos is array to sorting
// inicio is start of the partition (included)
// end is end of the partition (excluded)
// variante is the variable which select the pivot selection mode (0, 1 or 2)
void quickSort(int *arrayDatos, int inicio, int end, int variante) {
    int pivote, i, j, fin = end - 1;

    // vector size less than 2 -> dont do nothing
    if (end - inicio < 2)
        return;

    // vector size 2 -> check if is necessary swap it
    if (end - inicio == 2) {
        comparisons++;
        if (arrayDatos[inicio] > arrayDatos[fin]) {
            // No están ordenados los dos números, intercambiar
            intercambio(arrayDatos, inicio, fin);
        }
        return;
    }
    // vector size 3+
    switch (variante) {
    case 0: // Middle
        {
            int medio = inicio + (end - inicio) / 2;
            // swap pivot and last element
            intercambio(arrayDatos, medio, fin);
            break;
        }
    case 1: //Aleatory
        {
            int aleatorio = inicio + rand() % (end - inicio);
            // swap pivot and last element
            intercambio(arrayDatos, aleatorio, fin);
            break;
        }
    case 2: //Median of 3
        {
            int mediana = calcularMediana(arrayDatos, inicio, fin);
            // swap pivot and last element
            intercambio(arrayDatos, mediana, fin);
            break;
        }
    default:
        printf("Invalid pivot selection method %d.\n", variante);
        return;
    }
    pivote = arrayDatos[fin];
    // start partition
    for (i = inicio, j = fin - 1;;) {
        while ((i <= fin - 1) && ((void)comparisons++, arrayDatos[i] <= pivote)) {
            i++;
        }
        while ((j >= inicio) && ((void)comparisons++, pivote <= arrayDatos[j])) {
            j--;
        }
        if (i < j) { // swap numbers
            intercambio(arrayDatos, i, j);
            i++;
            j--;
        } else { // end partition
            break;
        }
    }
    // restore pivot
    intercambio(arrayDatos, i, fin);
    // end partition, recursive calls
    quickSort(arrayDatos, inicio, i, variante); // Vector de la izquierda del pivote
    quickSort(arrayDatos, i + 1, end, variante); // Vector de la derecha del pivote
}

/* up to 3 arguments can be passed to this program:
   - the array size
   - the pivot selection method
   - the maximum element value
 */
int main(int argc, char *argv[]) {
    int n = argc < 2 ? 100 : (int)strtol(argv[1], NULL, 0);
    int method = argc < 3 ? 2 : (int)strtol(argv[2], NULL, 0);
    int max = argc < 4 ? n - 1 : (int)strtol(argv[3], NULL, 0);
    int *a = malloc(n * sizeof(*a));

    if (a == NULL) {
        fprintf(stderr, "cannot allocate memory for %d elements\n", n);
        return 1;
    }
    for (int i = 0; i < n; i++) {
        a[i] = rand() % (max + 1);
    }

    printf("n=%d, m=%d, method=%d -> ", n, max, method);
    fflush(stdout);

    comparisons = exchanges = 0;
    quickSort(a, 0, n, method);

    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            fprintf(stderr, "ordering error: a[%d] = %d > a[%d] = %d\n",
                    i - 1, a[i - 1], i, a[i]);
            return 1;
        }
    }
    printf("%lld comparisons, %lld exchanges\n", comparisons, exchanges);
    return 0;
}

以下是一些运行时输出，显示该算法如何很好地处理随机数据，表现出 N log(N) 的预期平均时间复杂度，但很快就会降级到 N² 用于包含大量重复项的数据，最终由于堆栈溢出而导致大型统一数据集崩溃。

n=100000, m=99999, method=2 -> 1976491 comparisons, 469625 exchanges
n=100000, m=99999, method=1 -> 2047869 comparisons, 431256 exchanges
n=100000, m=99999, method=0 -> 2186895 comparisons, 424248 exchanges
n=100000, m=10, method=0 -> 436941482 comparisons, 228596 exchanges
n=100000, m=10, method=1 -> 393712217 comparisons, 226964 exchanges
n=100000, m=10, method=2 -> 385925150 comparisons, 234864 exchanges
n=100000, m=1, method=2 -> 3347387811 comparisons, 175168 exchanges
n=100000, m=0, method=2 -> Segmentation fault: 11

这里有一些改进实现的提示:

• 仅在较小的子范围上递归并在较大的子范围上迭代；
• 使用 Bentley McIlroy 方法隔离枢轴值的重复项；
• 将递归限制在几十个级别，并切换到病理集的堆排序，这可以用反 qsort 构建。