算法与数据结构全阶班-左程云版（二）基础阶段之3.归并排序和快速排序（上）

2022-11-24 126

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本文主要介绍了两种排序，归并排序和快速排序，归并排序有递归和非递归2种方式实现，快速排序的升级版为荷兰国旗问题。

前言

本文主要介绍了两种排序，归并排序和快速排序，归并排序有递归和非递归2种方式实现，快速排序的升级版为荷兰国旗问题。

1.归并排序

归并排序：

1)整体是递归，左边排好序+右边排好序+ merge让整体有序；

2)让其整体有序的过程里用了排外序方法；

3)利用master公式来求解时间复杂度；

4)可以用非递归实现。

递归方式举例如下：

实现如下：

// 递归方法实现
public static void mergeSort1(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
    // base case
    if (L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {
    int[] help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    System.arraycopy(help, 0, arr, L, help.length);
}

非递归方式举例如下：

实现如下：

// 非递归方法实现
public static void mergeSort2(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    int N = arr.length;
    int mergeSize = 1;      // 步长
    while (mergeSize < N) {
        int L = 0;          // 当前左组的第一个位置
        while (L < N) {
            if (L + mergeSize >= N) {
                break;
            }
            int M = L + mergeSize - 1;
            int R = Math.min(M + mergeSize, N - 1);
            merge(arr, L, M, R);
            L = R + 1;
        }
        // 防止溢出
        if (mergeSize > N / 2) {
            break;
        }
        mergeSize <<= 1;
    }
}

现在计算时间复杂度：

递归方式：

非递归方式：

综上，归并排序复杂度：T(N)= 2*T(N/2)+ O(N^1)

根据master可知时间复杂度为O(N*logN)

merge过程需要辅助数组，所以额外空间复杂度为O(N)

归并排序的实质是把比较行为变成了有序信息并传递，比O(N^2)的排序快

相比于冒泡排序、选择排序和插入排序O(N2)的时间复杂度，归并排序O(N*LogN)的时间复杂度优化了很多，这是因为减少了比较次数。

用常见面试题再深入理解一下归并排序的精髓。

在一个数组中，一个数组左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。

举例：[1,3,4,2,5]

1左边比1小的数︰没有

3左边比3小的数:1

4左边比4小的数:1、3

2左边比2小的数:1

5左边比5小的数: 1、3、4、2

所以数组的小和为1+1+3+1+1+3+4+2=16

基本思路：

左组的数小于右组的数时，产生小和，左指针右移；

左组的数等于右组时，直接拷贝右组，不产生小和；

左组的数大于右组时，直接拷贝右移，不产生小和。

小和产生的时候就是merge的时候，如下：

原理是：思路转换，从计算一个数左边更小的数之和转换为一个数右边更大的数之和。

实现如下：

public class SmallSum {
    public static int smallSum(int[] arr) {
        if (null == arr || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }
    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + (r - l) >> 1;
        return process(arr, l, mid)
                + process(arr, mid+1, r)
                + merge(arr, l, mid, r);
    }
    public static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l  + 1];
        int i = 0;
        int p1 = l, p2 = mid + 1;
        int res = 0;
        while (p1 <= mid && p2 <= r) {
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        System.arraycopy(help, 0, arr, l, help.length);
        return res;
    }
}