java - java实现QuickSort的一些问题

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