快速排序无限循环问题求助：rand()取模10时程序停滞

我明白你遇到的困扰了：当用rand()%10生成数组元素时，程序打印完未排序数组就停滞，但换成rand()%100却能正常运行。这是因为你的分区函数（partition）存在死循环逻辑，在重复元素较多的场景下（比如rand()%10更容易生成大量重复值）会被触发。

问题根源分析 #

1. 分区函数的死循环 #

当数组中存在大量与基准值p相等的元素时，外层while(i<=j)循环会陷入无限循环：

• 假设所有元素都等于基准值p，第一个内部while会让i一直递增到r+1（因为a[i]<=p始终成立）；
• 第二个内部while中，a[j]（此时j=r+1，全局数组未初始化的元素默认是0）小于p，所以j不会递减，保持r+1；
• 此时i==j==r+1，满足i<=j的条件，进入循环体交换同一位置的元素，之后循环重复执行，永远无法退出。

2. 多余的交换操作 #

循环结束后你额外执行了一次temp = a[i]; a[i] = a[j]; a[j] = temp;，这不仅多余，还会导致访问数组边界外的元素（比如r+1位置），引发未定义行为。

3. 快速排序调用参数错误 #

main函数中你调用quicksort(0,n-2)，数组的右边界应该是n-1（因为数组下标从0到n-1），否则最后一个元素永远不会被排序。

修复后的代码 #

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

int a[50];

void quicksort(int l, int r) {
    int s;
    if (l < r) {
        s = partition(l, r);
        quicksort(l, s - 1);
        quicksort(s + 1, r);
    }
}

int partition(int l, int r) {
    int p, i, j, temp;
    p = a[l];
    i = l;
    j = r; // 调整初始值为r，避免越界

    while (i < j) { // 外层循环条件改为i < j，避免无效循环
        // 找到第一个大于p的元素，增加边界检查
        while (i <= r && a[i] <= p) {
            i++;
        }
        // 找到第一个小于p的元素，增加边界检查
        while (j >= l && a[j] > p) {
            j--;
        }
        // 仅当i<j时执行交换，避免无意义操作
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    // 将基准值交换到正确的分区位置
    temp = a[l];
    a[l] = a[j];
    a[j] = temp;
    return j;
}

int main() {
    int n, i;
    printf("Enter number of elements: \n");
    scanf("%d", &n);
    printf("Random Array: \n");
    for (i = 0; i < n; i++) {
        a[i] = rand() % 10; // 现在用%10也能正常运行
        printf("%d ", a[i]);
    }
    quicksort(0, n - 1); // 修复右边界参数，确保所有元素被排序
    printf("\n Solution: \n");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

关键修复点说明 #

1. 调整分区函数的初始化与循环逻辑：

   • 将j的初始值从r+1改为r，避免一开始就访问数组边界外的元素；
   • 外层循环条件改为while(i < j)，防止i==j时进入无效循环；
   • 内部循环增加边界检查（i <= r和j >= l），确保不会越界；
   • 交换元素前先判断i < j，避免无意义的交换。

2. 移除多余的交换操作：

   • 删除了循环结束后多余的a[i]和a[j]交换，只保留基准值与j位置元素的交换，确保分区正确。

3. 修复快速排序的调用参数：

   • 将quicksort(0,n-2)改为quicksort(0,n-1)，确保所有元素都被纳入排序范围。

这样修改后，无论你用rand()%10还是rand()%100，程序都能正常运行，不会再出现停滞的情况。

内容的提问来源于stack exchange，提问作者apps