This is the review of subsets.

Quick sort

public void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }

        int index = rand.nextInt(end - start + 1)  + start;
        int pivot = A[index];
        int left = start;
        int right = end;

        //就当作自己的Pattern，这里用的<=，记住，免得以后边界错误
        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left ++;
            }
            while (left <= right && A[right] > pivot) {
                right --;
            }

            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;

                left ++;
                right --;
            }
        }
        // A[start... right] 这里用的right的原因是right已经比left小了，用right不会重复，下面用left同理
        quickSort(A, start, right);
        // A[left ... end]
        quickSort(A, left, end);
    }

Merge sort recursion

private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }

        int left = start, right = end;
        int mid = (start + end) / 2;

        mergeSort(A, start, mid, temp);
        mergeSort(A, mid+1, end, temp);
        merge(A, start, mid, end, temp);
    }

    private void merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid+1;
        int index = start;

        // merge two sorted subarrays in A to temp array
        while (left <= mid && right <= end) {
            if (A[left] < A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }

        // copy temp back to A
        for (index = start; index <= end; index++) {
            A[index] = temp[index];
        }
    }

Merge Sort non-recursion

    public void sortIntegers2(int[] A) {
        // write your code here
        int[] temp = new int[A.length];
        for (int size = 1; size < A.length; size = size * 2) {
            for (int i = 0; i < A.length - 1; i = i + size * 2) {
                int left = i;
                int right = Math.min(i + size * 2 - 1, A.length - 1);
                //这里mid容易出错，因为给right加了限制之后，忘记了给mid也加上这个限制，因为Mid也可以超下标
                int mid = Math.min(left + size -1, A.length - 1);
                merge(A, left, mid, right, temp);
            }
        }
    }

    private void merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid+1;
        int index = start;

        // merge two sorted subarrays in A to temp array
        while (left <= mid && right <= end) {
            if (A[left] < A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }

        // copy temp back to A
        for (index = start; index <= end; index++) {
            A[index] = temp[index];
        }
    }

Different Sort

• Merge sort 是稳定排序，如果有两个2，如果2有一个属性叫做先后，那么2先能排到2后前面
• Quick sort是不稳定排序，无法实现上述

Two Pointers Sort

• Many problem use the two pointers to sort, the most classic one is the color sort

Merge Sort Basic

Merge Sort Recursion

Merge Sort Recursion Improvement

Merge Sort Iterative

Quick Sort Basic

Quick Sort Partitioning

另一种写法 / 推荐用这一种

    public void quickSort(int[] nums){
        if (nums == null || nums.length == 0) {
            return;
        }
        sortHelper(nums, 0, nums.length - 1);
    }

    public void sortHelper(int[] nums, int start, int end){
        if (start >= end) {
            return;
        }
        int partitionPoint = partition(nums, start, end);
        sortHelper(nums, start, partitionPoint - 1);
        sortHelper(nums, partitionPoint + 1, end);

    }

    public void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

    public int partition(int[] nums, int start, int end){
        //int mid = start + (end - start)/2;
        int lo = start;
        int pivot = nums[lo];
        start++;
        while (start <= end) {
            while (start <= end && nums[start] < pivot) {
                start++;
            }
            while (start <= end && nums[end] > pivot) {
                end--;
            }
            if (start <= end) {
                swap(nums, start, end);
                start++;
                end--;
            }
        }
        //一定要--start,因为上一次交换start已经start = start + 1,而我们需要的是没有+1的start
        swap(nums, lo, --start);
        return start;
        //index = start前的,数组元素已经小于现在的nums[start],后面的大于
    }

Quick Sort Improve

Quick Select

Quick 3 Way