if v / s while: для этого кода, если я использую while l oop, оно продолжается бесконечно, но при использовании "if (low

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 и т. Д. Для Сопл (низкий + "" + высокий)

, но для ..

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 + разбиение алгоритм его печати 1 в повторении. Почему так себя ведет?

Answer 1

Ваш метод не изменяет значения low и high, поэтому условие l oop - (low < high) либо никогда не будет истинным (а l oop немедленно прекратится), либо всегда будет истинным (а l oop будет бесконечным).

Это рекурсивный алгоритм, поэтому вам не нужен al oop. Вам просто нужен оператор if, который определяет, должна ли рекурсия продолжаться или заканчиваться.

Answer 2

Как уже отвечено, while будет l oop навсегда, так как ни low, ни high не обновляются, поэтому вместо этого требуется if, поскольку он выполняется только один раз или не выполняется вообще.

A while обычно используется вместе с a, если это повторяется только в меньшем разделе, затем обновляет низкий или высокий уровень и возвращает цикл для большего раздела. Это ограничивает сложность стекового пространства 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;
        }
    }
}

Answer 3

С Операторы while и do-while

Оператор while вычисляет выражение, которое должно возвращать логическое значение. 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, поэтому бесконечно l oop.

Где как if-then Заявление

Оператор if-then является самым основным c из всех операторов потока управления. Он говорит вашей программе выполнить определенный фрагмент кода, только если конкретный тест оценивается как true.

Что еще более важно, в отличие от циклов, его выполнение выполняется только один, если условие является условным, поэтому в вашем случае он работает нормально. ,

для быстрой сортировки взглянуть Быстрая сортировка .