QuickSortC實作未按預期作業-有解無憂

我正在嘗試在 C 中實作 QuickSort 演算法，但這讓我很難過，我不知道我做錯了什么，但有時輸出不是我預期的：

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

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

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

int partition(int array[], int l, int r, int size) {
    int pivot_index = (l   r) / 2;
    int pivot = array[pivot_index];
    while (l < r) {
        while (l < size && pivot >= array[l])
            l  ;
        while (r >= 0 && pivot < array[r])
            r--;
        if (l < r)
            swap(&array[l], &array[r]);
    }
    swap(&array[pivot_index], &array[r]);
    return r;
}

void quickSort(int array[], int start, int end, int size) {
    int pivot;
    if (end > start) {
        pivot = partition(array, start, end, size);
        quickSort(array, start, pivot - 1, size);
        quickSort(array, pivot   1, end, size);
    }
}

int main() {
    int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
    printArray(array_test, (sizeof(array_test) / sizeof(array_test[0])));
    quickSort(array_test, 0,
              (sizeof(array_test) / sizeof(array_test[0])),
              (sizeof(array_test) / sizeof(array_test[0])));
    printArray(array_test, (sizeof(array_test) / sizeof(array_test[0])));
    return 0;
}

輸入陣列/輸出陣列：

948 4 0 89 7 34 1 3->3 1 4 0 7 34 89 948

9 8 7 6 5 4 3 2 1 0->0 1 2 4 3 5 6 7 8 9

9 8 7 59 6 5 4 6 3 0 2 1 0->0 0 1 2 3 5 4 6 6 9 7 8 59

954 485 0 345 1 36->954 36 0 1 345 485

如您所見，一些陣列給了我一些非常奇怪的結果，我真的不知道為什么，所以如果有人能幫我弄清楚，我將不勝感激。

uj5u.com熱心網友回復：

你的主要錯誤在這里

quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) , (sizeof(array_test) / sizeof(array_test[0])));

您為 size 和 end 傳遞了相同的值。你需要

quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) - 1 , (sizeof(array_test) / sizeof(array_test[0])));

同樣，當您進行大量索引雜耍時，您可以這樣做

int partition(int array[], int l, int r, int size) {
    assert(r > -1 && r < size);
    assert(l > -1 && l < size);

如果您使用無效索引，這將在您的除錯器中立即停止。這會發現你的錯誤

uj5u.com熱心網友回復：

您的代碼中有多個問題：

在中，您傳遞了一個太大main()的初始值：您應該傳遞.r(sizeof(array_test) / sizeof(array_test[0])) - 1
計算中間索引int pivot_index = (l r) / 2;是不正確的：它可能會在非常大的陣列上溢位。采用int pivot_index = l (r - l) / 2;
在partition()函式中，回圈測驗l < sizeandr >= 0是不正確的：您應該將landr與切片的邊界而不是完整陣列的邊界進行比較。
最后一條陳述句swap(&array[pivot_index], &array[r]);不正確，因為樞軸可能已移動。
事實上，r可能不是樞軸值的最終索引，因此遞回呼叫不應忽略此索引。消除樞軸索引的經典技巧是將樞軸交換到切片的開頭或結尾，然后將其交換回的最終值r。

這是修改后的版本：

#include <stdio.h>

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

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

int partition(int array[], int l, int r, int size) {
    int first = l;
    int last = r;
    int pivot_index = l   (r - l) / 2;
    int pivot = array[pivot_index];
    swap(&array[first], &array[pivot_index]);
    while (l < r) {
        while (l < last && pivot >= array[l])
            l  ;
        while (r > first && pivot < array[r])
            r--;
        if (l < r)
            swap(&array[l], &array[r]);
    }
    swap(&array[first], &array[r]);
    return r;
}

void quickSort(int array[], int start, int end, int size) {
    if (start < end) {
        int pivot = partition(array, start, end, size);
        quickSort(array, start, pivot - 1, size);
        quickSort(array, pivot   1, end, size);
    }
}

int main() {
    int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
    int array_length = sizeof(array_test) / sizeof(array_test[0]);
    printArray(array_test, array_length);
    quickSort(array_test, 0, array_length - 1, array_length);
    printArray(array_test, array_length);
    return 0;
}

請注意，函式size中未使用最后一個引數，并且partition()函式中不需要quickSort。實際上，將元素的數量傳遞給兩個函式并在遞回時調整陣列指標實際上不會那么混亂。

這是一個簡化版本：

#include <stdio.h>

void printArray(const int array[], int length) {
    for (int i = 0; i < length; i  )
        printf("%d ", array[i]);
    printf("\n");
}

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

int partition(int array[], int length) {
    int l = 1;
    int r = length - 1;
    int pivot_index = length / 2;
    int pivot = array[pivot_index];
    swap(&array[0], &array[pivot_index]);
    for (;;) {
        while (l < length - 1 && pivot >= array[l])
            l  ;
        while (r > 0 && pivot < array[r])
            r--;
        if (l < r)
            swap(&array[l], &array[r]);
        else
            break;
    }
    swap(&array[0], &array[r]);
    return r;
}

void quickSort(int array[], int length) {
    if (length > 1) {
        int pivot = partition(array, length);
        quickSort(array, pivot);
        quickSort(&array[pivot   1], length - pivot - 1);
    }
}

int main() {
    int array_test[] = { 948, 4, 0, 89, 7, 34, 1, 3 };
    int array_length = sizeof(array_test) / sizeof(array_test[0]);
    printArray(array_test, array_length);
    quickSort(array_test, array_length);
    printArray(array_test, array_length);
    return 0;
}

最后一項改進：在較小的一半上遞回限制了堆疊深度并避免了病理情況下的堆疊溢位：

void quickSort(int array[], int length) {
    while (length > 1) {
        int pivot = partition(array, length);
        if (pivot < length - pivot) {
            quickSort(array, pivot);
            array  = pivot   1;
            length -= pivot   1;
        } else {
            quickSort(&array[pivot   1], length - pivot - 1);
            length = pivot;
        }
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/444761.html

標籤：数组 C 排序快速排序

上一篇：c#查找偶數或奇數

下一篇：兩個陣列：在第一個中查找缺少的專案，在第二個中查找缺少的專案