Some issues in implementing QuickSort in java

问题:

Here is my code:

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

After running this program, it does not sort the array and prints the same array without sorting.

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

What is the wrong in this implementation?

回答1:

The problem is that your swap() function doesn't actually swap elements in an array, it just swaps the values in two integer variables. Integers are passed in Java by value, not by reference.

Replace this with a swap function that re-assigns the array values such as:

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

回答2:

Your swap function passes its parameters by value. Everthing is pass-by-value in java.

Your swap function needs to effectively pass by reference: See @matt b's answer above.

See Is Java pass by reference? for a good explanation of parameter passing.