在Java中实现QuickSort的一些问题 [英] Some issues in implementing QuickSort in java

问题描述

这是我的代码:

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

此实现中有什么问题?

推荐答案

问题是您的swap()函数实际上并不交换数组中的元素，它只是交换两个整数变量中的值.在Java中，整数是通过值而不是通过引用传递的.

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

这篇关于在Java中实现QuickSort的一些问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！