c++ - 关于快排的两个问题

Question

目前学习快排有两个问题。标准代码在这里(从我的书中复制):

void Quicksort(int a[], int low, int high){
    if(low<high){
      int pivotpos=Patrition(a,low,high);
      Quicksort(a,low,pivotpos-1);
      Quicksort(a,pivotpos+1,high);
    }
}
int Patrition(int a[], int low, int high){
    int pivot=a[low];  //first elemnent as pivot
    while(low<high){
        while(low<high&&a[high]>=pivot) --high;   //1
        a[low]=a[high];
        while(low<high&&a[low]<=pivot)  ++low;    //2
        a[high]=a[low];
   }
    a[low]=pivot;
    return low;     
}

我的问题在上面的代码中(标记为1和2):

一个。为什么当我在 1 中键入此程序时无法执行程序(核心转储): while(a[high]>=pivot) --high (与 2 类似)。看来我必须添加 condition(low<high)在第二个和第三个 while 循环中还是说核心已转储？

另一个问题是为什么必须有一个 operator=在第二个和第三个 while 循环中。我很困惑为什么当我输入 while(low<high&& a[high]>pivot 时它不起作用(与 2 类似)。如果我这样做，这个程序将一直循环，永远不会结束。

感谢您的关注。任何建议将不胜感激。

Answer 1

必须在每个 while 循环中写入 low < high 的原因是因为它首先检查第一个 while(大 while)的条件，开始循环，然后检查 while//1 中的条件并继续循环, 但在那段时间里，第一个 while 的(大的)条件从未被检查过。

例子:

a = 6;

while (a > 5) {
    while (a > 3) {
         --a;
    }
}

在这段代码中，第二个循环仅在 a = 3 时停止。

至于问题b，是因为它从来没有真正达到需要改变的值，因此从来没有真正对它进行排序。

示例:如果您希望循环在 a = 3 处停止，则以下循环将提前一步停止。

a = 5;
while (a > 4) {
     --a;
}

值 a 永远不会达到 3，它会在 a = 4 时停止，