if v/s while：对于这段代码，如果我使用 while 循环，它会无限循环，但是当使用 "if(low <high)" 时，它工作正常

Question

数组：4,1,5,8,2,6,9,7,11,3

public static void quickSort(int arr[], int low, int high) {
    System.out.println(low + " " + high);
    while(low < high) {
        int mid = quickPart(arr, low, high);            
        quickSort(arr, low, mid - 1);          
        quickSort(arr, mid + 1, high);
    }
}

它正在打印：0 0 然后是 2 1，然后是 0 0 和 2 1 等等 S.o.pl(low + " " + high)

但是对于..

public static void quickSort(int arr[], int low, int high) {
    System.out.println(low + " " + high);
    if(low < high) {
        int mid = quickPart(arr, low, high);            
        quickSort(arr, low, mid - 1);          
        quickSort(arr, mid + 1, high);
    }
}

它正在打印：0 9、0 1、0 0、2 1、3 9、3 3、5 9...它工作正常。

分区代码，如果有帮助..

public static int quickPart(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(pivot > arr[j]) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    System.out.println(i++);
    return i+1;
}

对于 if 语句，代码将在 low >= high 时终止，并且直到 9，即 9 > 9 终止但是对于 while + partitioning 算法，它会重复打印 1。为什么会这样？

Answer 1

您的方法不会更改 low 和 high 的值，因此循环的条件 - (low < high) 永远不会为真（循环将立即结束）或永远为真（并且循环将是无限的）。

这是一个递归算法，因此您不需要循环。您只需要一个 if 语句来确定递归是继续还是结束。

Answer 2

来自The while and do-while Statements

The while statement evaluates expression, which must return a boolean value. If the expression evaluates to true, the while statement executes the statement(s) in the while block. The while statement continues testing the expression and executing its block until the expression evaluates to false.

所以在你的 while(low < high) 这总是 true 这就是无限循环的原因。

其中 if-then Statement

The if-then statement is the most basic of all the control flow statements. It tells your program to execute a certain section of code only if a particular test evaluates to true.

更重要的是，与循环不同，如果条件为真，它只执行一个循环，这就是为什么它在您的情况下工作正常。

快速排序看一下QuickSort。

Answer 3

正如已经回答的那样，while 将永远循环，因为 low 或 high 都没有更新，所以需要一个 if 来代替，因为它只运行一次或根本不运行。

while 通常与 if 一起使用，它仅在较小的分区上递归，然后更新 low 或 high 并循环返回较大的分区。这将堆栈 space 的复杂度限制为 O(log(n))，但最坏情况下的时间复杂度仍然是 O(n^2)。

public static void quickSort(int arr[], int low, int high) {
    System.out.println(low + " " + high);
    while(low < high) {
        int mid = quickPart(arr, low, high);
        if((mid-low) <= (high-mid)){
            quickSort(arr, low, mid - 1);
            low = mid+1;
        } else {
            quickSort(arr, mid + 1, high);
            high = mid-1;
        }
    }
}

if v/s while：对于这段代码，如果我使用 while 循环，它会无限循环，但是当使用 "if(low <high)" 时，它工作正常

if v/s while: for this code if I'm using while loop it's continuing for infinite, but when used "if(low <high)" its working fine

java

recursion

if-statement

quicksort

while-loop