java - QuickSort 算法天真的实现..但为什么它不起作用？

Question

我是编程和 Java 的新手，所以请不要取笑 :)。现在..我在网上查看了 QuickSort 算法的正确实现，我知道这一点。但我试图以我能想到的非常天真、基本的方式自己实现它。实际上创建了两个单独的数组(左，右)并继续对它们进行排序等等...

这是代码:

package excercise;

public class MyQuickSort {


    public static int list[] = {6,5,3,1,8,7,2,4};


    public static int[] addNumberToArray(int array[],int num){
        int newArray[] = new int[array.length+1];
        for(int i = 0;i<array.length;i++){
            newArray[i] = array[i];
        }
        newArray[newArray.length-1] = num;
        array = newArray;
        return array;
    }


    public static int[] partition(int arr[]){

        while(arr.length>1){
            int pivotIndex = (int)(arr.length/2);
            int left[] = new int[0];
            int right[] = new int[0];

            for(int i = 0;i<arr.length;i++){
                if(i==pivotIndex){
                    continue;
                }

                else if(arr[i]<=arr[pivotIndex]){
                    left = addNumberToArray(left,arr[i]);
                }
                else{
                    right = addNumberToArray(right,arr[i]);
                }
            }
            int origPivot = arr[pivotIndex];
            int k = 0;
            while(k<left.length){
                arr[k] = left[k];
                k++;
            }
            arr[k] = origPivot;
            k++;
            while(k<arr.length){
                arr[k] = right[k-(left.length+1)];
            }


            if(left.length>1){
            partition(left);
            }

            if(right.length>1){
            partition(right);
            }

        }

            return arr;
    }




    public static void main(String[]args){
            list = partition(list);
            for(int i = 0;i<list.length;i++){
                System.out.print(list[i]+" ");
            }

        }
    }

但为什么这会陷入循环并且不起作用？我不明白这段代码有什么问题……除了这不是很有效(至少可以说)!但我很固执，无论如何都想尝试让它发挥作用……如果你有任何建议，那就太好了!提前谢谢

好的，这是新代码，调试后一切似乎都正常，但是当我想打印新的排序 arr 时，它仍然打印出原始的未排序数组。递归将整个事情转回到它开始的地方。我怎样才能让它“保存步骤”？我应该在哪里打“返回”电话，我应该返回什么？

public class MyQuickSort {

    public static int list[] = {6,5,3,1,8,7,2,4};
    public static boolean sorted;
    public static int[] addNumberToArray(int arr[],int num){
        int newArr[] = new int[arr.length+1];
        for(int i = 0;i<arr.length;i++){
            newArr[i] = arr[i];
        }
        newArr[newArr.length-1] = num;
        arr = newArr;
        return arr;

    }


    public static void partition(int arr[]){

        while(!sorted){
            int pivotIndex = (int)(arr.length/2);
            int left[] = new int[0];
            int right[] = new int[0];

            for(int i = 0;i<arr.length;i++){
                if(i==pivotIndex){
                    continue;
                }
                else if(arr[i]<=arr[pivotIndex]){
                    left = addNumberToArray(left,arr[i]);
                }
                else{
                    right = addNumberToArray(right,arr[i]);
                }
            }
            int origPivot = arr[pivotIndex];
            int k = 0;
            while(k<left.length){
                arr[k] = left[k];
                k++;
            }
            arr[k] = origPivot;
            k++;
            while(k<arr.length){
                arr[k] = right[arr.length-arr.length-(left.length+1)+k];
                k++;
            }


            if(left.length>1){
                partition(left);
            }


            if(right.length>1){
                partition(right);
            }

            if(left.length<=1&&right.length<=1){
                sorted = true;

            }

        }



    }








    public static void main(String[] args) {
        partition(list);
        for(int i = 0;i<list.length;i++){
            System.out.print(list[i]+" ");
        }


    }

}

Answer 1

你的算法陷入了这个循环

while(k<arr.length){
    arr[k] = right[k-(left.length+1)];
}

原因是您没有增加 k。

尝试

while(k<arr.length){
    arr[k] = right[k-(left.length+1)];
    k++;
}