Справка по Java Quicksort

Question

Я пытаюсь реализовать быструю сортировку в Java. Тем не менее, я испытываю странное поведение. Мой алгоритм работает на 70 элементов или меньше, но все, что выше, заставляет зависать все Java-приложение. это предел вызовов функций или объем используемой памяти?

Обычно я не использую быструю сортировку, поэтому моя реализация может быть немного неэффективной, но я думаю, что в целом логика верна:

int data[];

public void QuickSort(int start, int end)
{
            if(start == end || end < start || end > data.length)
            {
                return;
            }

            //find the pivot
            int pivotPos = (int)(start + (end - start) / 2);
            int temp;

            //switch the pivot to the end
            temp = data[pivotPos];
            data[pivotPos] = data[end];
            data[end] = temp;

            int LowerPoint = start;
            int HigherPoint = end - 1;

            //loop through and move low values down
            //and high values up
            while(LowerPoint != HigherPoint)
            {
                while(data[LowerPoint] < data[end] && LowerPoint < HigherPoint)
                {
                    LowerPoint++;
                }

                while(data[HigherPoint] > data[end]  && LowerPoint < HigherPoint)
                {
                    HigherPoint--;
                }

                if(LowerPoint != HigherPoint)
                {
                    temp = data[HigherPoint];
                    data[HigherPoint] = data[LowerPoint];
                    data[LowerPoint] = temp;
                }
            }

            //one last check to make sure we don't swap the pivot with a lower value
            //if this value is lower than increment our pointers up so we guarentee
            //the swap with a higher value
            if(data[LowerPoint] < data[end])
            {
                LowerPoint++;
                HigherPoint++;
            }

            //place the pivot back to the middle of the list
            //by swapping it with the higher point
            temp = data[HigherPoint];
            data[HigherPoint] = data[end];
            data[end] = temp;

            this.QuickSort(0, LowerPoint - 1);
            this.QuickSort(HigherPoint + 1, end);

        }

Любая помощь очень ценится.

Answer 1

Внимательно посмотрите на следующие 2 строки:

    this.QuickSort(0, LowerPoint - 1);
    this.QuickSort(HigherPoint + 1, end);

В них что-то не так.

Answer 2

Я реализовал быструю сортировку в своем последнем назначении, вот мой код, который может вам помочь:

public static void quickSort(int[] data, int first, int n)
{
    int p, n1, n2;
    if(n > 1)
    {
        p = partition(data, first, n);
        n1 = p - first;
        n2 = n - n1 - 1;
        quickSort(data, first, n1);
        quickSort(data, p+1, n2);
    }
}

public static void quickSort(int[] data)
{
    quickSort(data, 0, data.length);
}

private static int partition(int[] A, int first, int n )
{
    int right = first + n - 1;
    int ls = first;
    int pivot = A[first];
    for(int i = first+1; i <= right; i++)
    {
        if(A[i] <= pivot)
        // Move items smaller than pivot only, to location that would be at left of pivot
        {
            ls++;
            swap(A, i, ls);
        }
    }
    swap(A, first, ls);
    return ls;
}

private static void swap(int[] data, int pos1, int pos2)
{
    int temp = data[pos1];
    data[pos1] = data[pos2];
    data[pos2] = temp;
}