Quick sort

• Given an array arr, and an integer num. Place numbers less than or equal to num on the left side of the array, and numbers greater than num on the right side. Required extra space complexity O(1), time complexity O(N)

public static void partition1(int[] arrs, int num) {
        int small_index = 0;
        int bigger_index = arrs.length - 1;
        int index = 0;
        while (small_index < bigger_index) {
            int temp = arrs[index];
            if(temp<=num){
                arrs[index] = arrs[small_index];
                arrs[small_index] = temp;
                index++;
                small_index++;
            }else {
                arrs[index] = arrs[bigger_index];
                arrs[bigger_index] = temp;
                bigger_index--;
            }

        }

        System.out.println(Arrays.toString(arrs));
    }
Copy the code

• The Dutch flag
  • Given an array arr, and an integer num. Place numbers less than num on the left side of the array, numbers equal to num in the middle, and numbers greater than num on the right side of the array. Required extra space complexity O(1), time complexity O(N)

public static int[] netherlandsFlag(int[] arr, int L, int R) {
        if (L > R) {
            return new int[] { -1, -1 };
        }
        if (L == R) {
            return new int[] { L, R };
        }
        int less = L - 1;
        int more = R;
        int index = L;
        while (index < more) {
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                swap(arr, index++, ++less);
            } else {
                swap(arr, index, --more);
            }
        }
        swap(arr, more, R);
        return new int[] { less + 1, more };
    }
Copy the code

• Random fast row
  • Get a random number and place it at the rightmost end, then sort the whole array using Dutch flag algorithm to return less than the boundary and greater than the boundary.

public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag(arr, L, R);
        process(arr, L, equalArea[0] - 1);
        process(arr, equalArea[1] + 1, R);
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
Copy the code