public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};

        System.out.println("Before: " + Arrays.toString(array));
        sort1(array);
        System.out.println("After:  " + Arrays.toString(array));

        array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
        sort2(array);
        System.out.println("After:  " + Arrays.toString(array));

        array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
        sort3(array);
        System.out.println("After:  " + Arrays.toString(array));
    }

    public static void sort1(int[] arr) {
        recurse(arr, 0, arr.length - 1);
    }

    private static void recurse(int[] arr, int low, int high) {
        // low and high are both index
        if (arr.length <= 0) {
            return;
        }

        if (low >= high) return;

        int left = low;
        int right = high;

        // use another variable to keep the first element of the given array arr[low:high]
        // pivot serves as the pivot value.
        int pivot = arr[left];

        while (left < right) {

            // move values that smaller than pivot to the left
            while (left < right && arr[right] >= pivot) {
                right--;
            }

            // initially, value in slot left is copied by pivot, so it will not miss the original value if
            // we conduct following assignment.
            arr[left] = arr[right];

            // move values that greater than pivot to the right
            while (left < right && arr[left] <= pivot) {
                left++;
            }

            // value in slot right already transferred, it is fine to overwrite it.
            arr[right] = arr[left];
        }

        // do not miss to fill in the pivot value
        arr[left] = pivot;

        recurse(arr, low, left - 1);
        recurse(arr, left + 1, high);
    }

    public static void sort2(int[] arr) {
        // Non-recursion schema, adopt a stack to keep the partition ranges

        if (arr.length <= 0) {
            return;
        }

        Stack<Integer> stack = new Stack<>();

        stack.push(0);
        stack.push(arr.length - 1);
        while (!stack.isEmpty()) {
            int high = stack.pop();
            int low = stack.pop();

            int pivotIdx = partition(arr, low, high);

            if (pivotIdx > low) {
                stack.push(low);
                stack.push(pivotIdx - 1);
            }

            if (pivotIdx < high && pivotIdx >= 0) {
                stack.push(pivotIdx + 1);
                stack.push(high);
            }
        }
    }


    public static void sort3(int[] arr) {
        // Another non-recursion schema, adopt a queue to keep the partition ranges

        if (arr.length <= 0) {
            return;
        }

        Queue<Integer> queue = new ArrayDeque<>();

        queue.offer(0);
        queue.offer(arr.length - 1);
        while (!queue.isEmpty()) {

            // a slight difference with stack, low comes out first, then high
            int low = queue.poll();
            int high = queue.poll();

            int pivotIdx = partition(arr, low, high);

            if (pivotIdx > low) {
                queue.offer(low);
                queue.offer(pivotIdx - 1);
            }

            if (pivotIdx < high && pivotIdx >= 0) {
                queue.offer(pivotIdx + 1);
                queue.offer(high);
            }
        }
    }

    private static int partition(int[] arr, int low, int high) {
        if (arr.length <= 0) {
            return -1;
        }

        if (low >= high) {
            return -1;
        }

        int left = low;
        int right = high;

        int pivot = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }

            arr[left] = arr[right];

            while (left < right && arr[left] <= pivot) {
                left++;
            }

            arr[right] = arr[left];
        }

        arr[left] = pivot;

        return left;
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 14:51:54

results matching ""

    No results matching ""