Некоторые проблемы в реализации QuickSort в Java

Question

Вот мой код:

public class Main
{
    public static void main(String[] args)
    {
        int[] temp = {4,2,6,4,5,2,9,7,11,0,-1,4,-5};
        quickSort(temp);
        for(int s : temp) System.out.println(s);
    }

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

    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);
        }
    }

    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], A[ls]);
            }
        }
        swap(A[first], A[ls]);
        return ls;
    }

    private static void swap(int i, int j)
    {
        int temp = i;
        i = j;
        j = temp;
    }
}

После запуска этой программы она не сортирует массив и печатает тот же массив без сортировки.

4
2
6
4
5
2
9
7
11
0
-1
4
-5

Что не так в этой реализации?

Answer 1

Проблема в том, что ваша функция swap() на самом деле не меняет местами элементы в массиве, она просто меняет значения в двух целочисленных переменных.Целые числа передаются в Java по значению, а не по ссылке.

Замените это функцией подкачки, которая переназначает значения массива, такие как:

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

Answer 2

Ваша функция подкачки передает свои параметры по значению.В Java все передается по значению.

Ваша функция подкачки должна эффективно передавать по ссылке: см. Ответ @matt b выше.

См. Является ли Java передачей по ссылке? для хорошего объяснения передачи параметров.