Java List/Recursion bug

Question

Java新手.我正在关注一本书,并给出了一个关于quicksort的例子.我理解算法,但希望在每次递归之前打印数组,以真正了解较低和较高数组的情况.

我以为我只是声明一个单独的列表并用较低的值,枢轴和更高的值填充它,但它似乎抛弃了所有的功能.递归似乎保持不变但实际上并没有排序.因此,它溢出并退出.

我几乎可以肯定,我在这里缺少一个基本的Java概念.

除了评论中包含的内容之外的所有内容都来自本书.注释行之间的界限是我自己的.

package quicksort;

import java.util.ArrayList;
import java.util.List;

public class App {

    public static List<Integer> quicksort(List<Integer> numbers){
        if (numbers.size() < 2){
            return numbers;
        }

        final Integer pivot = numbers.get(0);
        final List<Integer> lower = new ArrayList<>();
        final List<Integer> higher = new ArrayList<>();

        for (int i = 1; i < numbers.size(); i++){
            if (numbers.get(i) < pivot){
                lower.add(numbers.get(i));
            }
            else{
                    higher.add(numbers.get(i));
            }
        }

        // Makes things go all squirrrrrrrrely
        final List<Integer> notYetSorted = lower;
        notYetSorted.add(pivot);
        notYetSorted.addAll(higher);

        System.out.println("During: " + notYetSorted);
        // -------------

        final List<Integer> sorted = quicksort(lower);

        sorted.add(pivot);

        sorted.addAll(quicksort(higher));

        return sorted;
    }

    public static void main(String[] args) {
        List<Integer> intList = new ArrayList<>();

        intList.add(5);
        intList.add(8);
        intList.add(2);
        intList.add(9);
        intList.add(10);
        intList.add(3);
        intList.add(4);
        intList.add(7);
        intList.add(1);
        intList.add(6);

        System.out.println("Before: " + intList);
        System.out.println("After: " + quicksort(intList).toString());
    }  

}

Answer 1

你的问题出现在这个块的开头:

final List<Integer> notYetSorted = lower;
notYetSorted.add(pivot);
notYetSorted.addAll(higher);

System.out.println("During: " + notYetSorted);
// -------------

final List<Integer> sorted = quicksort(lower);

与C++不同,当您将新变量分配给现有变量时,Java不会执行深层复制.因此notYetSorted,lower实际上在内存中引用完全相同的列表 - 您所做的任何更改也都会notYetSorted被执行lower.

因此,在该块的最后一行中,您List始终以与您开始时相同的大小调用快速排序.这就是为什么它会永远地复存.

将第一行更改为:

final List<Integer> notYetSorted = new ArrayList<>(lower);

一切都应该好.