各种排序算法总结及java实现

字数统计: 3k   |   阅读时长≈ 14 分钟

总结一下各种排序算法

时间复杂度

常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。具体来说，在常数操作数量的表达式中，
只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N)，那么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间。、

空间复杂度

为了支持算法的顺利运行，额外需要多少辅助空间

先定义一下基本的交换操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// i和j必须是不同位置的数（内存上是两个不同位置的数）
public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}


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

^ 异或运算，有以下四个性质
N ^ 0 = N
N ^ N = 0
如果 a ^ b = c 则，a = b ^ c,b = a ^ c
异或运算满足交换律和结合律

递归行为和递归行为时间复杂度的估算

一个递归行为的例子
master公式的使用
T(N) = a*T(N/b) + O(N^d)

1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d*logN)
3) log(b,a) < d -> 复杂度为O(N^d)

对数器的概念和使用

0，有一个你想要测的方法a，
1，实现一个绝对正确但是复杂度不好的方法b，
2，实现一个随机样本产生器
3，实现比对的方法
4，把方法a和方法b比对很多次来验证方法a是否正确。
5，如果有一个样本使得比对出错，打印样本分析是哪个方法出错
6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

冒泡排序

从第0个位置开始遍历，大的往后移，直到最大的数移动到最后一个位置。遍历完一遍之后，最后一个位置就不用管了，然后重复上面的步骤。
时间复杂度o(N^2)，额外空间复杂度o(1)

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
        for (int i = 0; i < e; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
}

选择排序

记第一个数为最小数，从第1个位置开始遍历，比较得到最小数的位置(index)，第1遍遍历完后，交换index与0位置的数字，接着从第2个位置重复上面的操作
时间复杂度o(N^2)，额外空间复杂度o(1)

1
2
3
4
5
6
7
8
9
10
11
12
public static void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

插入排序

假设数组前面基本有序，从1位置开始不断把数字插入到前面有序的数组中
时间复杂度o(N^2)，额外空间复杂度o(1)
最坏情况是o(N^2),最好情况(数组已经有序)是o(N)

1
2
3
4
5
6
7
8
9
10
public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 1; i < arr.length; i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

归并排序

递归的让左边部分有序，递归的让右边部分有序，再让整体有序。
时间复杂度o(N * log(N))，额外空间复杂度O(N)
时间省在哪：
比较行为没有浪费，之前的三种每遍历一次进行的比较，只确定了一个数的顺序，太多的比较被浪费
归并是组与组之间的比较，组内不管，比较行为得到了充分的利用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}

public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {    //递归终止条件
        return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);        // o(N/2)
    mergeSort(arr, mid + 1, r);    //o(N/2)
    merge(arr, l, mid, r);         //o(N)
}

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++];
    }
    //p1和p2一定有一个越界，有一个不越界
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void mergeSortNotDigui(int[] a) {
    if (a == null || a.length < 2)
        return;
    int interval = 1;
    while (interval < a.length) {
        int i = 0;
        for (i = 0; i < a.length; i += (interval + 1)) {
            int r = i + interval;
            if (r > a.length - 1)
                r = a.length - 1;
            merge(a, i, (i + r) / 2, r);
        }
        interval = 2 * interval + 1;     // 需要设置好间隔
    }
    merge(a, 0, interval / 2, a.length - 1);   //merge最后一次
}

小和问题和逆序对问题

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组
的小和。
例子：
[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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    return mergeSort(arr, 0, arr.length - 1);
}

public static int mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return 0;
    }
    int mid = l + ((r - l) >> 1);   //防止溢出
    return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}

public static int 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;
    int res = 0;
    while (p1 <= m && 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 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
    return res;
}

逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static int count = 0;
    public static void mergeSort(int[] a){
        if(a == null || a.length < 2)
            return;

        mergeSort(a,0,a.length - 1);
    }

    private static void mergeSort(int[] a, int l, int r) {
        if(l < r){
            int mid = l + ((r - l) >> 1);
            mergeSort(a,l,mid);
            mergeSort(a,mid + 1,r);
            merge(a,l,mid,r);
        }
    }

    private static void merge(int[] a, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = help.length - 1;   //从大开始统计
        int pl = mid;
        int pr = r;
        while (pl >= l && pr >= mid + 1){
            if(a[pl] > a[pr])
            {
                for(int j = mid + 1;j <= pr;j ++)
                {
                    System.out.println(a[pl] + " " + a[j]);
                    count ++;
                }
            }

            help[i --] = a[pl] > a[pr] ? a[pl --] : a[pr --];
        }
        while (pl >= l){
            help[i --] = a[pl --];
        }
        while (pr >= mid  + 1){
            help[i --] = a[pr --];
        }
        for (i = 0;i < help.length;i ++){
            a[l + i] = help[i];
        }

    }

merge过程中要从大到小开始排序，不能从小开始排序，不然会重复统计，而且统计不全

快速排序

parition过程

先随机选一个数和最后一个位置交换，在从左到右遍历，经过比较交换后，小于最后一个数的都放左边，大于最后一个数的都放在右边，等于的都在中间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] partition(int[] a,int l,int r){

    int index = l;
    int less = l - 1;
    int more = r;
    while (index < more){
        if(a[index] < a[r]){
            swap(a,++ less, index ++);
        }
        else if(a[index] > a[r]){
            swap(a,-- more,index);
        }
        else {
            index ++;
        }
    }
    swap(a,more,r);

    return new int[]{less + 1,more};  //返回中间相等数的第一个下标和最后一个下标
}

快排

递归重复上面过程
最好情况下时间复杂度o(N * log(N))，额外空间复杂度o(log(N))
最坏情况下时间复杂度o(N ^ 2)，额外空间复杂度o(N)
但由于中间的数是随机选择的，所以总体期望是
时间复杂度o(N * log(N))，额外空间复杂度o(log(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void quickSort(int[] a) {
    if (a == null || a.length < 2)
        return;
    quickSort(a, 0, a.length - 1);
}

public static void quickSort(int[] a,int l,int r){
    if(l < r){
        swap(a,l + (int)(Math.random() * (r - l + 1)),r);
        int[] res = partition(a,l,r);
        quickSort(a,l,res[0] - 1);
        quickSort(a,res[1] + 1,r);
    }
}

堆排序

时间复杂度O(N * logN)，额外空间复杂度O(1)

堆结构

堆是一个完全二叉树
从0位置开始的一段连续数组可以对应一个完全二叉树
即当前位置为i，左孩子为2 * i + 1，右孩子为2 * i + 2，父节点(i > 0)位置为(i - 1) / 2
堆可分为大顶堆和小顶堆
大顶堆，根节点为最大值
小顶堆，根节点为最小值

堆有两种调整
插入数据，向上调整(建立堆，时间复杂度为o(N))
移除堆顶数据，向下调整(时间复杂度O(N * logN))

节点i的高度为log(i)

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void heapSort(int[] a) {
    if (a == null || a.length < 2)
        return;

    for (int i = 0; i < a.length; i++) {
        heapInsert(a, i);
    }

    int size = a.length;
    while (size > 0) {
        swap(a, 0, --size);
        heapify(a, 0, size);
    }

}

public static void heapInsert(int[] a, int i) {
    while (a[(i - 1) / 2] < a[i]) {
        swap(a, (i - 1) / 2, i);
        i = (i - 1) / 2;
    }
}

public static void heapify(int[] a, int i, int size) {

    int l = 2 * i + 1;
    while (l < size) {
        int bigger_pos = l + 1 < size && a[l + 1] > a[l] ? l + 1 : l;

        if (a[i] < a[bigger_pos]) {
            swap(a, i, bigger_pos);
        } else {
            break;
        }
        i = bigger_pos;
        l = 2 * i + 1;
    }
}

排序算法稳定性比较

排序算法 稳定性 时间复杂度 额外空间复杂度
冒泡排序 稳定 o(N^2) o(1)
选择排序 不稳定 o(N^2) o(1)
插入排序 稳定 o(N^2) o(1)
归并排序 稳定 o(N * log(N)) o(N)
快速排序 不稳定 o(N * log(N)) o(log(N))
堆排序 不稳定 o(N * log(N)) o(1)

以上都是基于比较的排序
额外知识
归并排序额外空间复杂度可变成o(1)，即归并排序的内部缓存法，但会变成不稳定的
快速排序可以做到稳定性问题，额外空间复杂度会变成o(N)，但是非常难，可以搜”01 stable sort”

额外的排序

希尔排序

改进的插入排序，即逐渐调整步长的插入排序

非基于比较的排序

桶排序

数组中的数字在一定范围内，一个时间复杂度为o(N)的排序
桶就是容器，可以是数组，栈，队列等
示例
对一个大小在0-60之间的数组排序，申请一个数组大小为61的数组，初始化为0
对要排序的数组进行遍历，用大小为61的数组记录数字出现的次数即可，遍历完后，打印大小为61的数组(即桶)，大于0的就打印

打赏

请我喝杯咖啡吧~

支付宝
微信