08 归并排序和快排序

1 归并排序

思路：准备一个help数组，进行merge操作

 public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }
    public static void process(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        //求中点
        int mid = left + ((right - left) >> 1);
        process(arr, left, mid);
        process(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    //进行merge操作
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int l = left;
        int r = mid + 1;
        int i = 0;
        while (l <= mid && r <= right) {
            help[i++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
        }
        while (r <= right) {
            help[i++] = arr[r++];
        }
        while (l <= mid) {
            help[i++] = arr[l++];
        }
        System.arraycopy(help, 0, arr, left, help.length);
    }

public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 1;
        int length = arr.length;
        while (step < length) {
            int left = 0;
            while (left < length) {
                int mid = 0;
                //考虑边界和溢出
                if (length - left > step) {
                    mid = left + step - 1;
                } else {
                    mid = length - 1;
                }
                //考虑边界和溢出
                int right = 0;
                if (length - mid - 1 > step) {
                    right = mid + step;
                } else {
                    right = length - 1;
                }
                merge(arr, left, mid, right);
                if (right == length - 1) {
                    break;
                } else {
                    left = right + 1;
                }
            }
            if (step > (length >> 1)) {
                break;
            }
            step *= 2;
        }
    }
     public static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int l = left;
        int r = mid + 1;
        int i = 0;
        while (l <= mid && r <= right) {
            help[i++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
        }
        while (r <= right) {
            help[i++] = arr[r++];
        }
        while (l <= mid) {
            help[i++] = arr[l++];
        }
        System.arraycopy(help, 0, arr, left, help.length);
    }

2 快速排序

不改进的
1）把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：左侧<划分值、中间==划分值、右侧>划分值
2）对左侧范围和右侧范围，递归执行
3）时间复杂度：

 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 left, int right) {
        if (left >= right) {
            return;
        }
        int[] equalE = partition(arr, left, right);
        process(arr, left, equalE[0] - 1);
        process(arr, equalE[1] + 1, right);
    }
    public static int[] partition(int[] arr, int left, int right) {
        int lessR = left - 1;
        int moreL = right;
        int i = left;
        while (i < moreL) {
            if (arr[i] < arr[right]) {
                swap(arr, ++lessR, i++);
            } else if (arr[i] > arr[right]) {
                swap(arr, i, --moreL);
            } else {
                i++;
            }
        }
        swap(arr, moreL, right);
        return new int[]{lessR + 1, moreL};
    }

改进的
1）在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：左侧<划分值、中间==划分值、右侧>划分值
2）对左侧范围和右侧范围，递归执行
3）时间复杂度为:
4）额外空间复杂度：

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 left, int right) {
        if (left >= right) {
            return;
        }
        //等概率随机选一个值作为划分值
        swap(arr,left+(int) (Math.random()*(right-left+1)),right);

        int[] equalE = partition(arr, left, right);
        process(arr, left, equalE[0] - 1);
        process(arr, equalE[1] + 1, right);
    }


    public static int[] partition(int[] arr, int left, int right) {
        int lessR = left - 1;
        int moreL = right;
        int i = left;
        while (i < moreL) {
            if (arr[i] < arr[right]) {
                swap(arr, ++lessR, i++);
            } else if (arr[i] > arr[right]) {
                swap(arr, i, --moreL);
            } else {
                i++;
            }
        }
        swap(arr, moreL, right);
        return new int[]{lessR + 1, moreL};
    }