Выпуск быстрой сортировки в Java - PullRequest
Новая
       1

Выпуск быстрой сортировки в Java

2 голосов
/ 06 марта 2020

Я пытаюсь реализовать быструю сортировку, используя рекурсию и несколько методов, чтобы помочь. Когда я запускаю программу, я получаю сообщение о том, что я вышел за границы, сообщая мне, что я отклонился от индекса -1 массива. Кто-нибудь может дать совет по исправлению моего метода быстрой сортировки? (в этом и заключается проблема). Я знаю, что другие мои методы верны.

Пример {7,6,5,4,3,2,1}

должен получиться {1,2,3,4,5,6,7} 

public static <T extends Comparable<? super T>> void quickSort(T[] a) {
        quickSort(a,0,a.length - 1);
    }

    public static <T extends Comparable<? super T>> void quickSort(T[] a,int start,int end) { 
        if(start<end) {
            int pivotIndex = partition(a, start, end);
            quickSort(a,start,pivotIndex-1); // sort left partition
            quickSort(a,pivotIndex+1,end); // sort right partition
        }

    }

    public static <T extends Comparable<? super T>> int partition(T[] a, int start, int end) {
        int mid =midpoint(start,end);
        sortFirstMiddleLast(a,start,mid,end);


        swap(a,mid,end-1);
        int pivotIndex = end -1 ;
        T pivotValue = a[pivotIndex];

        int indexFromLeft = start +1 ;
        int indexFromRight = end -2;
        boolean done = false;
        while (!done) {
            while (a[indexFromLeft].compareTo(pivotValue)<0) {
                indexFromLeft++;
                }
            while (a[indexFromRight].compareTo(pivotValue)>0) {
                indexFromRight--;
            }
            if (indexFromLeft < indexFromRight) {
                swap(a,indexFromLeft,indexFromRight);
                indexFromLeft++;
                indexFromRight--;
            }
            else {
                done=true;
            }

        }
            swap(a,pivotIndex,indexFromLeft);
            pivotIndex=indexFromLeft;

        return pivotIndex;
    }

    public static <T extends Comparable<? super T>> void sortFirstMiddleLast(T[] a, int start, int mid, int end) {
        if (a[start].compareTo(a[mid])>0) {
            swap(a,start,mid);
        }
        else if (a[mid].compareTo(a[end])>0) {
            swap(a,mid,end);
        }
        else if (a[start].compareTo(a[end])>0) {
            swap(a,start,end);
        }
        else if(a[start].compareTo(a[mid])>0) {
            swap (a,start,mid);
        }

        }

    private static int midpoint(int first, int last) {
            return first + (last - first) / 2;
        }

private static void swap(Object[] a, int first, int second) {
        Object temp = a[first];
        a[first] = a[second];
        a[second] = temp;
    }

1 Ответ

0 голосов
/ 06 марта 2020

Код является разновидностью схемы разбиения Hoare. Предполагая, что вы не хотите добавлять проверку диапазона во внутренние циклы, элемент pivot должен находиться в диапазоне между левым и правым индексами. Если после двух внутренних циклов следует использовать левый индекс <= правый индекс (не <). </p>

Другая проблема заключается в том, что при типичной схеме разбиения Hoare pivot или elements = pivot могут заканчиваться где угодно, и Индекс, возвращаемый разделом, может не быть осью. Индекс просто разбивает массив на элементы <= pivot и elements> = pivot (опять же, elements == pivot или сам pivot может оказаться где угодно). Это означает, что вызывающий код не может исключить возвращенный индекс из рекурсивных вызовов. Также для типичной схемы разбиения Hoare последний элемент не может использоваться для сводки, поскольку это может привести к бесконечной рекурсии. В вики-статье приведен пример быстрой увеличения и предварительного уменьшения быстрой сортировки на основе Hoare.

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Пример C код для увеличения и уменьшения записи изменение схемы разбиения Hoare с объединением логики c в функцию быстрой сортировки. Для этого конкретного варианта схемы разбиения Hoare любой элемент, включая последний элемент, может быть использован для сводки, но выбор первого или последнего элемента для сводки приводит к сложности времени O (n ^ 2) для наихудшего случая для уже отсортированной или обратной последовательности. отсортированные данные, а выбор среднего элемента, как показано ниже, приводит к наилучшему поведению для уже отсортированных или обратно отсортированных данных. 

void QuickSort(int a[], int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + (hi-lo)/2];
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);
}
...