c - C 中的快速排序无限循环？

Question

我在快速排序算法中遇到无限循环问题，这种情况发生在右子数组分区中，因此如果我只对左子数组进行分区，它会像这段代码一样工作得很好。

#include <stdio.h>
int list[] = {8, 1, 3, 4, 2, 10, 4, 6};
//int list[] = {2, 1, 10, 4, 5, 11, 12, 6};
//int list[] = {1, 2, 4,  5, 6, 11, 12, 10};
int main(int argc, char **argv)
{

    printf("Unsorted list is: ");
    printArray(list);
    quickSort(list, 0, 7);
    //partition(list, 5, 7);
    printf("Sorted list is: ");
    printArray(list);

    return 0;
}

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

void quickSort(int list[], int low, int high){

    int pIndex = partition(list, low, high);

    if(pIndex <= 0){
        return;
    }

    //quick sort left sub array
    quickSort(list, low, pIndex-1);

    //quick sort right sub array
//  quickSort(list, pIndex+1, high);

    printf("pIndex is %d\n", pIndex);
}

int partition(int list[], int low, int high){
    int pivot = list[high];


    int i;
    int j = high - 1;
//  int j = high;


    while( 1 ){
        //less than pivot
        for(i = 0; list[i] < pivot; i++){
            printf("for %d (index %dth) < %d\n", list[i], i, pivot);
            //do nothing
        }
        printf("less than stop at index %d which is %d\n", i, list[i]);

        //more than pivot
        for(j = j; j > 0 && pivot < list[j]; j--){
            printf("for %d < %d (index %dth)\n", pivot, list[j], j);
        }
        printf("greater than stop at index %d which is %d\n", j, list[j]);

        if(i >= j){
        printf("low index %d >= %d then swap pivot\n", i, j);
        printf("swap index %dth which is %d, with index pivot %d which is %d\n", i, list[i], high, list[high]);
        swap(list, i, high);

        printf("Temporary list is: ");
        printArray(list);

        printf("then return last position index pivot %d which is %d\n", i, list[i]);
        return i;
        break;
        }

        //tukarPosisi, sehingga yang kecil di sebelah kiri, yang besar di sebelah kanan.
        printf("swap index %dth which is %d, with index %dth, which is %d\n", i, list[i], j, list[j]);
        swap(list, i, j);

        printf("Temporary list is: ");
        printArray(list);


    }
}

void swap(int list[], int i, int j){
    //variabel sementara untuk menampung i
    int temporary = list[i];

    //tukar posisi, sehingga yg kecil di kiri, yg besar di kanan.
    list[i] = list[j];
    list[j] = temporary;
}

我已经打印了很多调试信息，但仍然不明白为什么会发生这种情况。那么逻辑错误在哪里以及如何修复呢？

任何帮助将不胜感激

Answer 1

您的代码存在几个问题，主要影响其效率而不是其正确性。其中一些在评论中被提出。然而，最大的问题是递归的终止条件，正如您所期望的，考虑到错误行为的性质。

具体来说，当 partition() 返回小于或等于零的值时，递归就会触底，但该函数始终返回为枢轴选择的最终位置。如果您仅向下递归分区的左侧，那么您最终肯定会得到零，但是当您向下递归任何不包含元素 0 的分区时，partition() 永远不会返回 0。

您应该根据要排序的段的大小(即高 - 低)来中断递归。如果它小于 1，那么您可以停止，因为少于两个元素的段肯定已经按顺序排列。