Что не так с моей реализацией быстрой сортировки Java?

Question

Я почти уверен, что понимаю, как работает быстрая сортировка, но я не могу найти ошибку, из-за которой моя попытка реализовать ее не работает.Я просматривал это часами и не могу понять, что не так.Пожалуйста, помогите мне!Вот весь файл (это просто быстрая сортировка - ничего лишнего. Массив - это просто случайные числа для проверки быстрой сортировки.)

public class Quicksort{ 

    public static void main(String args[]){
        int[] arr = {5,1,4,3,7,0,9,2,6,8};
        quicksort(arr, 0, arr.length-1);
        for(int x : arr)
          System.out.print(x+" ");
    }

    public static void quicksort(int[] arr, int start, int end){
        if(end-start<2)
            return; 
        int pivot = (end-start)/2;
        int i = start; 
        int k = end;
        while(k>i){
            while(arr[i]<arr[pivot]&&k>i&&i<=end)
                i++; 
            while(arr[k]>arr[pivot]&&k>=i)
                k--; 
            if(k>i){
                swap(arr, i, k); 
            }
        }
        swap(arr, pivot, i);

        quicksort(arr, 0, i);
        quicksort(arr, k, arr.length-1);
     }

     public static void swap(int[] a, int x, int y){
         int temp = a[x]; 
         a[x] = a[y]; 
         a[y] = temp; 
     }
}

Как сейчас, цикл никогда не заканчивается ... это навсегдабесконечный цикл!Пожалуйста, помогите мне понять, что не так.

Answer 1

Сделайте себе одолжение и научитесь пользоваться отладчиком . Это делает решение таких проблем очень простым.

Answer 2

Несколько вещей, которые выделяются -

1. Ваше конечное состояние кажется неверным.Если в вашем массиве всего 2 элемента, он не будет сортировать их.

2. Кроме того, после выполнения свопинга вам нужно увеличивать, а i и уменьшать k.

Answer 3

Ваш базовый регистр должен быть if(end-start<1) - вы хотите прекратить сортировку только тогда, когда количество элементов равно 1 (т. Е. Если start и end равны)

Ваши циклы while должны быть просто while(arr[i]<arr[pivot]) и while(arr[k]>arr[pivot])

Это

if(k>i){
    swap(arr, i, k); 
}

должно быть

if(k>=i){
    swap(arr, i, k);
    i++;
    k--;
}

swap(arr, pivot, i); не требуется.

Ваш рекурсивный вызов должен быть quicksort(arr, start, k); и quicksort(arr, i, end);

Answer 4

while(arr[i]<arr[pivot]&&k>i&&i<=end)

Очевидно, у вас были проблемы с индексами массива.Все эти тесты не требуются для работающей быстрой сортировки, а те, которые находятся в неправильном порядке.