如何在Java中正确实现QuickSort的递归？

Question

我目前正在使用Java开发QuickSort，并且已经成功地为第一次迭代对列表进行了排序。但是，我的递归实现未执行我想要的操作。这可能是什么原因？

列表为[11，4，53，65，44，23，202，37，1]

...
quickSort(list, 0, list.size() - 1);
...

public static List<Integer> quickSort(List<Integer> l1, int from, int to) {
        if (l1.size() < 2)
            return l1;
        int pivot = l1.get(to);
        int counterLastSwapPos = 0;
        int counter = from;
        while (counter < l1.indexOf(pivot)) {
            if (l1.get(counter) >= pivot)
                counter++;
            else {
                int temp = l1.get(counter);
                l1.set(counter, l1.get(counterLastSwapPos));
                l1.set(counterLastSwapPos, temp);
                counterLastSwapPos++;
            }
            System.out.println(l1);
        }
        quickSort(l1, 0, l1.indexOf(pivot));
        quickSort(l1, l1.indexOf(pivot) + 1, l1.size());
        return l1;
    }

Answer 1

Java中快速排序的

这里是正确的实现方式（升序）。

 public static List<Integer> quickSort(List<Integer> l1, int from, int to) {
        System.out.println("Quick Sort \n");
        long startTime = System.nanoTime();

        if (l1.size() < 2)
            return l1;
        //select a pivot - the last element of the list
        int pivot = l1.get(to - 1);
        //introduce two counters:
        int counterLastSwapPos = 0;//this first one will track the index of the element
        //that is bigger than the pivot - we start from zero (we never actually
        // know that this number is actually bigger - it is a 
        // presupposition)
        for (int counter = 0; counter < l1.indexOf(pivot); counter++) {
            //we also have a counter to track our position during the iteration
            //if the element at the current position is smaller than the pivot -
            //swap the element(current position) with the element that is bigger 
            //than the pivot.
            if (l1.get(counter) < pivot) {
                int temp = l1.get(counter);
                l1.set(counter, l1.get(counterLastSwapPos));
                l1.set(counterLastSwapPos, temp);
                //Once the swap has happened - increment the counter
                //that tracks the number bigger than the pivot
                counterLastSwapPos++;
                //finally, in the loop, the position counter will be 
                //automatically incremented 
            }
            //when the position counter reaches the last allowed position,
            //swap the pivot with the the counter that tracks 
            // the number bigger than the pivot
            if (counter == l1.indexOf(pivot) - 1) {
                l1.set(l1.indexOf(pivot), l1.get(counterLastSwapPos));
                l1.set(counterLastSwapPos, pivot);
            }
        }
        //as this sorting is a "Divide&Conquer" type, we use recursion to perform
        //the same operations on two parts of the list. That is why, (if you scroll up),
        //you'll see that once the list becomes size of 1, the recursion will stop.
        //Our pivot is now somewhere in the middle - this was our aim.
        //Now, pay attention to perform the recursion on
        //two lists/arrays that WILL NOT include the pivot itself
        List<Integer> left = l1.subList(from, l1.indexOf(pivot));
        quickSort(left, 0, left.size() - 1);
        List<Integer> right = l1.subList(l1.indexOf(pivot) + 1, to);
        quickSort(right, 0, right.size());
        //list is sorted
        long endTime = System.nanoTime();
        long duration = (endTime - startTime);
        System.out.println("Time: " + duration + "\n");
        return l1;
    }