java - java实现QuickSort的一些问题

标签 java quicksort sorting

这是我的代码:

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

这个实现有什么问题?

最佳答案

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

将其替换为交换函数,该函数重新分配数组值,例如:

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

关于java - java实现QuickSort的一些问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6039012/

相关文章:

java - 如何在android中持久化一个对象?

java - MySQL Java 存储过程给出错误 "Parameter index of 1 is out of range"

java - 设置数组格式以将文本以表格格式附加到 TextField 中

objective-c - iOS:如何使用 NSSortDescriptor 对关系中的值进行排序?

linq - 如何在linq查询中应用多个orderby

java - 让 ENTER 像使用 JTextField 一样使用 JSpinner

delphi - 自定义 QuickSort 实现中的 SIGSEGV

idris 中的快速排序

java - 快速排序算法的动画

jquery - 数据表排序: make one column stay fixed