使用一种方法进行快速排序

Question

我的教授要求我使用快速排序算法对整数数组进行排序，但没有对使用方法进行优化。他说，程序必须包含在一种方法上。我的问题是，这是可能的吗？如果是这样，你们中的任何一个人都可以演示，因为他只教了我们关于冒泡排序算法的知识。

Answer 1

是的，这可以用一种方法来完成。整个递归可以通过使用循环和堆栈来迭代完成。因此，快速排序算法可以重写为：

public class Main {

    @FunctionalInterface
    public interface Func {
        void call(int[] arr, int i, int j);
    }

    public static void main(String[] args) {
        int[] numbers = {45, 123, 12, 3, 656, 32};
        System.out.println("Unsorted array: " + Arrays.toString(numbers));

        // store swap function as a lambda to avoid code duplication
        Func swap = (int[] arr, int i, int j) -> {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        };

        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(numbers.length);

        while (!stack.isEmpty()) {
            int end = stack.pop();
            int start = stack.pop();
            if (end - start < 2) {
                continue;
            }

            // partitioning part
            int position = start + ((end - start) / 2);
            int low = start;
            int high = end - 2;
            int piv = numbers[position];
            swap.call(numbers, position, end - 1);
            while (low < high) {
                if (numbers[low] < piv) {
                    low++;
                } else if (numbers[high] >= piv) {
                    high--;
                } else {
                    swap.call(numbers, low, high);
                }
            }
            position = high;
            if (numbers[high] < piv) {
                position++;
            }
            swap.call(numbers, end - 1, position);
            // end partitioning part

            stack.push(position + 1);
            stack.push(end);
            stack.push(start);
            stack.push(position);
        }

        System.out.println("Sorted array: " + Arrays.toString(numbers));
    }
}