randomized_quicksort

Question

这段代码没有显示任何输出

#include <cstdlib>
#include <iostream>
using namespace std;

int partition(int a[], int left, int right) {
    int i = left;
    int j = right;

    int temp;
    int pivot = a[left];

    while(i <= j) {
        while(a[i] < pivot)
             i++;

        while(a[j] > pivot)
            j--;
            if(i>j) break;

            if (i<j){
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
    }
    return i;
}

int randomized_partition(int a[], int left, int right){
    int t = left + rand() % (right - left + 1);

    std::swap(a[right], a[t]);
    return partition(a, left, right);
}

void randomized_quicksort(int a[], int l, int r){
    if(l> = r) return;

    int q = randomized_partition(a, l, r);
    randomized_quicksort(a, l, q-1);
    randomized_quicksort(a, q+1, r);
}

int main(){
    int a[] = {12, 6, 4, 7, 9, 10, 11, 14, 13, 19, 18, 21, 20};
    int n = sizeof(a) / sizeof(n);
    randomized_quicksort(a, 0, n-1);

    for (int i = 0; i < n; i++){
        cout << a[i] << "  " << endl;
    }
    return 0;
}

它是算法第三版中引入的randomized_quicksort,请帮忙

Answer 1

程序卡在调用中partition(2, 4).数组的相关部分当时是6, 9, 7,所以pivot初始化为6.

你进入主while循环,i循环立即终止,因为它总是第一次出现,因为a[i] == pivot.所以你进入j循环,它执行两次因为7并且9都大于pivot,它仍然是6.因为,j循环终止.j == 2a[j] == pivot

继续前进,第一个条件是false因为i不大于j.第二个条件是false因为i不小于j.这标志着主while循环的结束,所以我们检查循环的条件并发现它是true因为i等于j.我们没有更改任何数组元素的值,因此内部while循环永远不会再次运行,并且条件仍然存在false.你陷入了无限循环,从未取得任何进展.

仔细看看你的教科书.要么是书中有错误,要么是你错误地抄写了它.