о быстрой сортировке

Question

Я написал этот код, но он напечатает эти следы стека в консоли, пожалуйста, помогите мне, спасибо!(Также «p» и «q» являются первым и последним индексом нашего массива соответственно)

public class JavaQuickSort {

public static void QuickSort(int A[], int p, int q) {
    int i, last = 0;

    Random rand = new Random();
    if (q < 1) {
        return;
    }
    **swap(A, p, rand.nextInt() % (q+1));**

    for (i = p + 1; i <= q; i++) {
        if (A[i] < A[p]) {
            swap(A, ++last, i);
        }

    }
    swap(A, p, last);
    QuickSort(A, p, last - 1);
    QuickSort(A, last + 1, q);
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    **A[i] = A[j];**
    A[j] = temp;


}
public static void main(String[] args){
    int[] A = {2,5,7,3,9,0,1,6,8};
    **QuickSort(A, 0,8 );**
    System.out.println(Arrays.toString(A));
}
}

трассировки стека:

run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -3
        at JavaQuickSort.swap(JavaQuickSort.java:38)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:22)
        at JavaQuickSort.main(JavaQuickSort.java:45)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

Я также выделил жирным шрифтом те выражения, которые вызываютэти следы стека.как ==> ** ... **

РЕДАКТИРОВАНИЕ:

public class JavaQuickSort {

public static void QuickSort(int arr[],int lo,int hi) {
    int n = arr.length;
    if(n<=1)
        return;
    **int r = partition(arr);**
    **QuickSort(arr,lo , r-1);**
    QuickSort(arr, r+1, hi);
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    **A[i] = A[j];**
    A[j] = temp;


}
public static int partition(int arr[]){
      int i, last = 0;
 Random rand = new Random();
    int n = arr.length;
    if (n <= 1)
        return arr[0];

    **swap(arr, 0, rand.nextInt(n));**

    for (i =1; i <n; i++) {
        if (arr[i] < arr[0]) {
            swap(arr, ++last, i);
        }

    }
    swap(arr, 0, last);
    return last;
}
public static void main(String[] args){
    int[] A = {2,5,7,3,9,0,1,6,8};
    **QuickSort(A, 0,8 );**
    System.out.println(Arrays.toString(A));
}
}

Я отредактировал свой пост, чтобы он был более понятным, и он напечатает эти следы стека, и я выделю строки, которыевызвать эти следы стека !!!

следы стека:

run:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at JavaQuickSort.swap(JavaQuickSort.java:27)
        at JavaQuickSort.partition(JavaQuickSort.java:39)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:19)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.QuickSort(JavaQuickSort.java:20)
        at JavaQuickSort.main(JavaQuickSort.java:52)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

пожалуйста, помогите мне спасибо

РЕДАКТИРОВАНИЕ:

Я написал этот код собращая внимание на первый ответ этого поста, но он не будет сортировать мой массив !!!

public class JavaQuickSort {

public static void QuickSort(int arr[], int lo, int hi) {
    if (hi > lo) {
         Random rand = new Random();
        int pivotIndex = lo + rand.nextInt(hi-lo+1);
        int pivotnewIndex = partition(arr, lo, hi,pivotIndex);
        QuickSort(arr, lo, pivotnewIndex - 1);
        QuickSort(arr, pivotnewIndex + 1, hi);
    }
}

private static void swap(int[] A, int i, int j) {
    int temp;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;


}

public static int partition(int arr[],int lo,int hi,int pivotIndex)
{
    int pivotValue = arr[pivotIndex];
    swap(arr, hi, pivotIndex);
    int storeIndex = lo;
    for(int i = lo;i<hi;i++){
        if (arr[i]<=pivotValue)
        swap(arr, storeIndex, i);
        storeIndex = storeIndex ++;
    }
    swap(arr, storeIndex, hi);
    return storeIndex;

}

public static void main(String[] args) {
    int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
    QuickSort(A, 0, 8);
    System.out.println(Arrays.toString(A));
}
}

вывод:

run:
[2, 9, 3, 8, 0, 6, 7, 1, 5]
BUILD SUCCESSFUL (total time: 2 seconds)

Мне нужна ваша помощь, я действительно запутался !!!

Answer 1

Некоторые проблемы с вашим кодом:

• Не создавайте новый экземпляр Random для однократного использования. Просто создайте его один раз, сохраните в, скажем, поле static, а затем используйте его для генерации множества случайных чисел для вашего приложения.
• При создании случайного индекса для пивота он должен находиться в диапазоне от p до q включительно.
• Используйте перегрузку Random.nextInt(int n) для генерации случайного числа в заданном диапазоне
• Возможно, используйте lo и hi вместо p и q и int[] arr вместо int A[]
• Вы можете получить длину массива с помощью .length member

Что касается самого алгоритма быстрой сортировки, он не похож ни на что, что я видел раньше. Я рекомендую изучить стандартную императивную реализацию и адаптировать ее.

Смотри также

• Википедия / Quicksort

---

Обновление

К сожалению, вы несколько перепутали псевдокоды из Википедии. Вы хотите адаптировать этот алгоритм:

  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right - 1 // left ≤ i < right  
         if array[i] ≤ pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

  procedure quicksort(array, left, right)
     if right > left
         select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

Обратите внимание, что вышеприведенный алгоритм выбирает средний элемент подмассива между left и right для сводного индекса. Поскольку вам нужна рандомизированная быстрая сортировка, вы хотите выбрать случайный индекс от left до right включительно, поэтому формулу необходимо изменить следующим образом:

  pivotIndex := left + (random number between 0 and right-left inclusive)

Так, например, если left = 5 и right = 7, то вы хотите, чтобы pivotIndex было 5 + x, где x - случайное число от 0 до 7-5=2 включительно.

Поскольку Random.nextInt(n) имеет исключительную верхнюю границу, перевод этого на Java будет выглядеть примерно так:

int pivotIndex = lo + rand.nextInt(hi - lo + 1);

---

Окончательная коррекция

Вы сделали распространенную ошибку для начинающих здесь:

    // HORRIBLE FORMATTING! Don't do this!
    if (arr[i]<=pivotValue)
    swap(arr, storeIndex, i);
    storeIndex = storeIndex ++;

Если вы заметили приведенный выше псевдокод, предполагается, что оба оператора являются частью тела if, но приведенный выше код с правильными отступами и добавлением фигурных скобок действительно такой:

    // PROPER FORMATTING! Reveals bug instantly!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex, i);
    }
    storeIndex = storeIndex ++;

Таким образом, исправление заключается в перемещении приращения storeIndex в тело if следующим образом:

    // Corrected according to pseudocode!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex, i);
        storeIndex = storeIndex ++;
    }

Или вы также можете просто сделать:

    // Nice and clear!
    if (arr[i]<=pivotValue) {
        swap(arr, storeIndex++, i);
    }

Уроки этого последнего обновления:

• Всегда делайте отступ в своем коде правильно
  • Хорошая IDE может сделать это бризом, у вас действительно нет оправдания
• Привыкнуть к скобкам if, даже если они не являются строго необходимыми.
  • Многие тонкие ошибки связаны с отсутствием скобок
• Разумно используйте пост / предварительные приращения
  • Как и многие вещи, ими можно злоупотреблять за пределами понимания, но при правильном и идиоматическом использовании они приводят к краткому и читабельному коду

---

Последняя вещь

Когда я упоминал .length массивов, я имел в виду, что вместо этого:

int[] A = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(A, 0, 8); // BAD! Don't hardcode array length!

Вы должны сделать это:

int[] arr = {2, 5, 7, 3, 9, 0, 1, 6, 8};
QuickSort(arr, 0, arr.length - 1); // GOOD!

Answer 2

Поскольку это , а не домашнее задание, и я бы взял категорию домашнее задание для самообучения, вам следует просто использовать стандарт Arrays.sort(int[]).

Answer 3

swap(A, p, rand.nextInt() % (q+1));

Произведенное случайное целое число может быть ниже p, очевидно, вы хотите, чтобы оно было между p и q.

Answer 4

Генератор случайных чисел выдает положительные и отрицательные значения. Вот почему в конце концов вы вызываете swap с отрицательным значением q.