排序算法全解析

发表于 | 分类于 |

时间复杂度$O(n^2)$级排序算法

冒泡排序

冒泡排序是入门级的算法。通常来说，冒泡排序有三种写法：

  • 一边比较一边向后两两交换，将最大值/最小值冒泡到最后一位；
  • 经过优化写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生过交换表示已经有序，不需要再继续排序；

  • 进一步优化的写法：除了使用一个变量记录当前轮次是否发生过交换，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

冒泡排序的第一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bubbleSort(int[] num){
    for(int i = 0; i < num.length; i++){
        for(int j = 0; j < num.length - 1 - i; j++){
            //若左边的数值大于右边的数组，则交换，保证右边的数字最大
            if(num[j] > num[j+1]){
                swap(num, i, i+1);
            }
        }
    }
}

//交换元素
private static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

总共的比较次数为$(n-1)+(n-2)+(n-3)+…+1$。

冒泡排序的第二种写法

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
public static void bubbleSort(int[] num){
    //定义一个标志变量用于记录是否发生了交换，初始为true，确保正常运行
    boolean flag = true;
    for(int i = 0; i < num.length; i++){
        //判断是否发生过了交换，若未交换则直接退出
        if(!flag){
            break;
        }
        //将标志变为false
        flag = false;
        for(int j = 0; j < num.length - 1 - i; j++){
            if(num[i] > num[i+1]){
                swap(num, i, i+1);
                //发生了交换，将标志置为true
                flag = true;
            }
        }
    }
}

//交换元素
private static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

冒泡排序的第三种写法

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
public static void bubbleSort(int[] num){
	//记录是否发生交换的变量
    boolean flag = true;
    //记录最后一个没有经过排序元素的索引位置
    int indexOfLast = num.length() - 1;
    //记录上一次交换的索引位置
    int swappedIndex = -1;
    
    while(flag){
        flag = false;
        for(int i = 0; i < indexOfLast; i++){
            if(num[i] > num[i+1]){
                swap(num, i. i+1);
                flag = true;
                //记录交换的位置
                swappedIndex = i;
            }
        }
        //最后一个没有经过排序的元素的下标就是最后交换的位置
        indexOfLast = swappedIndex;
    }
}

//交换元素
private static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

交换的技巧

一般来说，交换数组中两个数字的函数如下：

1
2
3
4
5
private static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

如何在不引入第三种中间变量的情况下，完成两个数字的交换。

1
2
3
num[j+1] = num[j] + num[j+1];
num[j] = num[j+1] - num[j];
num[j+1] = num[j+1] - num[j];

还有一种先减后加的写法：

1
2
3
num[j+1] = num[j] - num[j+1];
num[j] = num[j] - num[j+1];
num[j+1] = num[j+1] + num[j];

但这两种方式都可能导致数字越界。

更好的方式是通过位运算完成数字交换：

1
2
3
num[i] = num[i] ^ num[j];
num[j] = num[j] ^ num[i];
num[i] = num[i] ^ num[j];

时间复杂度和空间复杂度

冒泡排序的空间复杂度为：$O(1)$​，时间复杂度为：$O(n^{2})$，第二种、第三种冒泡排序由经过优化，最好的情况下只需要$O(n)$的时间复杂度。

最好的情况为：在数组已经有序的情况下，由于没有发生交换，排序结束。

最坏情况：数组逆序，每次比较都会发生交换。

优化后的冒泡排序平均时间复杂度仍然是$O(n^{2})$，所以这些优化对算法的性能并没有质的提升。

把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

1
2
3
4
输入: [10,2]
输出: "102"
输入: [3,30,34,5,9]
输出: "3033459"
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
class Solution {
    public String minNumber(int[] nums) {
        //corner case
        if(nums == null || nums.length == 0){
            return "";
        }
        //将数组转为字符串数组
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            str[i] = nums[i] + "";
        }

        //对字符数组进行排序，排序的方式为：比较两个数字前加后后加后的大小
        Arrays.sort(str, (a, b) -> (a+b).compareTo(b+a));

        //对排序完毕的字符串数组进行拼接
        //创建一个StringBuilder来保存结果
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < str.length; i++){
            res.append(str[i]);
        }

        return res.toString();
    }
}

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void moveZeroes(int[] nums) {
        //使用双指针，左指针记录不为0的最右边的索引，右指针遍历
        //左指针左边都不为0，右指针左边到左指针都为0
        int i = 0, j = 0;
        while(j < nums.length){
            //若右指针不为0则与左指针交换
            if(nums[j] != 0){
                swap(nums, i, j);
                i++;
            }
            j++;
        }
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

选择排序

选择排序的思想是：双重遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] nums){
    //记录最小值的下标
    int minIndex = 0;
    for(int i = 0; i < nums.length; i++){
        minIndex = i;
        for(int j = i+1; j < nums.length; j++){
            //若右边的小于当前的，则记录最小值的下标
            if(nums[minIndex] > nums[j]){
                minIndex = j;
            }
        }
        //交换最小元素
        int temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
}

选择排序，每一轮都找到当前的最小值，将最小值交换至本轮首位。

冒泡排序和选择排序有什么异同点？

相同点：

  • 都是两层循环，时间复杂度为：$O(n^{2})$​
  • 都只使用有限个变量，空间复杂度为：$O(1)$

不同点：

  • 冒泡排序在比较过程中就不断交换；而选择排序增加了一个变量保存最小值/最大值的下标，遍历完成后才交换，减少了交换次数。
  • 冒泡排序是稳定的，选择排序是不稳定的

排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且在r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则为不稳定的。

二元选择排序

选择排序算法也可以进行优化，既然每轮遍历找出了最小值，何不把最大值也找出来？这就是二元选择排序的思想。

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
public static void selectSort2(int[] nums){
    //两个变量一个记录最小值索引，一个记录最大值索引
    int minIndex = 0, maxIndex = 0;
    for(int i = 0; i < (nums.length >> 1); i++){
        minIndex = i;
        maxIndex = i;
        for(int j = i+1; j < nums.length; j++){
            if(nums[minIndex] > nums[j]){
                //记录最小值
                minIndex = j;
            }
            if(nums[maxIndex] < nums[j]){
                //记录最大值
                maxIndex = j;
            }
        }
        //若minIndex和maxIndex相等，那么必定等于i，此时已经排好
        if(minIndex == maxIndex){
            break;
        }
        //将最小元素交换到头部
        int temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
        
        //若最大值的索引为i，由于已经发生交换，所以需要更新maxIndex的值
        if(maxIndex = i){
            maxIndex = minIndex;
        }
        //将最大元素交换到尾部
        temp = nums[nums.length - 1 - i];
        nums[nums.length - 1 - i] = nums[maxIndex];
        nums[maxIndex] = temp;
    }
}

时间复杂度和空间复杂度

选择排序使用两层循环，时间复杂度为$O(n^{2})$；只使用有限个变量，空间复杂度为$O(1)$。二元选择排序虽然比选择排序要快，但无法改变时间复杂度，二元选择排序的时间复杂度$O(n^{2})$；只使用有限个变量，空间复杂度为$O(1)$。

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第k 个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k` 个不同的元素。

1
2
3
4
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //使用插排找出第K个最大
        int maxIndex = 0;
        for(int i = 0; i < k; i++){
            maxIndex = i;
            for(int j = i+1; j < nums.length; j++){
                if(nums[maxIndex] < nums[j]){
                    maxIndex = j;
                }
            }

            int temp = nums[maxIndex];
            nums[maxIndex] = nums[i];
            nums[i] = temp;
        }

        return nums[k-1];
    }
}

插入排序

插入排序的思想非常简单，生活中一个常见的场景：在打扑克牌的时候，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手中已有的牌中合适的位置，逐渐完成整个排序。

插入排序有两种写法：

  • 交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置
  • 移动法：在新数字插入的过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当数字找到自己的位置后，插入一次即可。

交换法插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void insertSort(int[] nums){
    //从第二个数字开始，第一个数字默认有序
    for(int i = 1; i < nums.length; i++){
        for(int j = i; j > 0; j--){
            //向前遍历查找
            if(nums[j] < nums[j-1]){
                swap(nums, j ,j-1);
            }else{
                break;
            }
        }
    }
}

//交换元素
private static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

插入排序的过程不会破坏原有数组中相同关键字的相对次序，所以插入排序是一种稳定的排序算法。

时间复杂度和空间复杂度

插入排序过程需要两层循环，时间复杂度为：$O(n^{2})$；空间复杂度为：$O(1)$。

对链表进行插入排序

对链表进行插入排序。

1
2
3
4
输入: 4->2->1->3
输出: 1->2->3->4
输入: -1->5->3->4->0
输出: -1->0->3->4->5
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
46
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        //构建一个dummy节点
        ListNode dummy = new ListNode(-1, head);
        //记录有序的最后一个节点
        ListNode finish = head;
        //记录当前需要排序的节点
        ListNode cur = head.next;

        while(cur != null){
            //若需要排序的节点值>=已完成的值则直接修改当前
            if(cur.val >= finish.val){
                finish = finish.next;
            }else{
                //否则从头开始遍历找到位置插入
                ListNode pre = dummy;
                while(pre.next.val <= cur.val){
                    pre = pre.next;
                }
                //插入节点
                finish.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
                
            }
            //跟新节点
            cur = finish.next;
        }

        return dummy.next;
    }
}

时间复杂度$O(nlogn)$级排序算法

希尔排序

由美国辛辛那提大学的数学博士(Donald Shell)在《ACM通讯》上发表了希尔排序算法，成为首批时间复杂度降到$O(n^{2})$以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是$O(n^{2})$，但经过优化的希尔排序可以达到$O(n^{1.3})$甚至$O(n^{7/6})$。

希尔排序本质是对插入排序的一种优化，它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。它的基本思想是：

  • 将待排序的数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组；
  • 逐渐缩小间隔进行下一轮排序；
  • 最后一轮，取间隔为1，也就相当于直接使用插入排序。但这时经过前面的【宏观调控】，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void Shell(int[] nums){
    //增量序列
    int N = nums.length;
    int h = 1;
    while(h < N/3){
        h = 3 * h + 1;
    }
    for(int gap = h; gap > 0; gap = (gap-1)/3){
        for(int i = gap; i < N; i++){
            for(int j = i; (j > gap - 1) && (nums[j] < nums[j-gap]); j -= gap){
                
                swap(nums, j, j-gap);
            }
        }
    }
}

//交换元素
private static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

虽然插入排序是稳定的排序算法，但希尔排序不是稳定的。在增量较大时，排序过程可能会破坏原有数组中相同关键字的相对次序。

时间复杂度和空间复杂度

事实上，希尔排序的时间复杂度非常难以分析，它的平均复杂度界于$O(n)$到$O(n^{2})$之间，普遍认为它最好的时间复杂度为$O(n^{1.3})$。希尔排序的空间复杂度为：$O(1)$。

堆排序

快速排序

快速排序算法由C.A.R.Hoare在1960年提出。它的时间复杂度也是$O(nlogn)$，但它的时间复杂度为$O(nlogn)$级的几种排序算法中，大多数情况下效率更高，所以快速排序的应用非常广泛。

快速排序的基本思想是：

  • 从数组中取出一个数，称之为基数(pivot)
  • 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
  • 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成。

事实上，快速排序的每一次遍历，都将基数摆到最终位置上。第一轮遍历排好1个基数，第二轮遍历排好2个基数，第三轮遍历排好4个基数，以此类推。总遍历次数为$logn$~$n$次，每轮遍历的时间复杂度为$O(n)$，所以很容易分析出来快速排序的时间复杂度为$O(nlogn)$~$O(n^{2})$，平均时间复杂度为$O(nlogn)$。

快速排序递归框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void quickSort(int[] nums){
    quickSort(nums, 0, nums.length-1);
}

private static void quickSort(int[] nums. int lo, int hi){
    //将数组分区，并获得中间值的索引
    int mid = partition(nums, lo, hi);
    //对左边区域进行快排
    quickSort(nums, lo, mid-1);
    //对右边区域进行快排
    quickSort(nums, mid+1, hi);
}

private static int partition(int[] nums, int lo, int hi){
    //将nums数组从lo-hi分区，左边区比基数小，由边区比基数大，最后返回中间基数的索引
}

退出递归的边界条件

很容易想到，当某个区域只剩下一个数字的时候，自然不需要排序了，此时推出递归函数。

1
2
3
4
5
6
7
8
9
10
11
12
private static void quickSort(int[] nums. int lo, int hi){
    //边界条件
    if(lo >= hi){
        return;
    }
    //将数组分区，并获得中间值的索引
    int mid = partition(nums, lo, hi);
    //对左边区域进行快排
    quickSort(nums, lo, mid-1);
    //对右边区域进行快排
    quickSort(nums, mid+1, hi);
}

分区算法实现

快速排序中最重要的便是分区算法，也就是partition函数。partition函数需要做的事情就是将nums从lo到hi分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标。那么首先我们要做的事情就是选择一个基数，基数我们一般称为pivot，意味“轴”。整个数组就像围绕这个轴进行旋转，小于轴的数字旋转到左边，大于轴的数字旋转到右边。(双轴快排就是一次选取两个基数，将数组分为三个区域进行旋转。)

基数的选择

基数的选择没有固定的标准，随意地选择区间任何一个数字做基数都可以，通常来讲有三种选择方式：

  • 选择第一个元素作为基数
  • 选择最后一个元素作为基数
  • 选择区间内一个随机元素作为基数

选择的基数不同，算法的实现也不同。实际上第三种选择方式的平均时间复杂度是最优的。

最简单的分区算法

分区方式也有很多种，最简单的思路是：从left开始，遇到比基数大的数，记录其下标；再从right往前遍历，找到第一个比基数小的数，记录其下标；然后交换这两个数。继续遍历，直到left和right相遇。最后交换基数和中间值，并返回中间值的索引。

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
private static int partition(int[] nums, int lo, int hi){
    //将nums数组从lo-hi分区，左边区比基数小，由边区比基数大，最后返回中间基数的索引
    int pivot = nums[lo];
    int i = lo, j = hi+1;
    while(true){
        //找到第一个比基数大的数的索引
        while(nums[++i] < pivot){
            if(i == hi){
                break;
            }
        }
        //找到第一个比基数小的数的索引
        while(nums[--j] > pivot){
            if(j == lo){
                break;
            }
        }
        //若i>=j直接退出
        if(i >= j){
            break;
        }else{
            swap(nums, i, j);
        }
    }
    //将基数和轴交换
    swap(nums, lo, j);
    return j;
}

private static void swap(int[] nums, int i,int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

快速排序是一种不稳定的排序算法，在分区过程中，相同数字的相对顺序可能被修改。

时间复杂度和空间复杂度

快速排序的时间复杂度，平均情况下为：$O(nlogn)$，最坏的时间复杂度为$O(n^{2})$，空间复杂度与递归的层数有关，每层递归会产生一些临时变量，所以空间复杂度为：$O(logn)$~$O(n)$，平均空间复杂度为：$O(logn)$。

为什么说随机选择剩余数组中的一个元素作为基数的方案平均复杂度最优呢？先要知道什么情况下快速排序算法的时间复杂度最高，一共有两种情况：

  • 数组为正序
  • 数组为逆序

理想中的快速排序在第K轮遍历中，可以排好$2^{k-1}$个基数。但当在数组为正序或逆序时，我们将第一个数作为基数的话，每轮分区后，都有一个区域是空的，也就是说数组剩下的数组都被分到同一个区域！就导致了每一轮遍历只能排好一个基数。所以总的比较次数为$(n-1)+(n-2)+…+1$，此时快速排序的时间复杂度达到了$O(n^{2})$级。

解决的思路也很简单，只要每轮选择的基数不是剩余数组中最大或最小的值就可以了。具体方案有很多，比较常用的有三种。

快速排序的优化思想

第一种就是我们在前文中提到的，每轮选择基数时，从剩余的数组中随机选择一个数字作为基数。这样每轮都选到最大或最小值的概率就会变得很低。所以我们才说这种方式选择基数，其平均时间复杂度是最优的。

第二种解决方案是在排序之前，先用洗牌算法将数组的原有顺序打乱，以防止原数组正序或逆序。Java将洗牌算法封装到集合类中，即Collections.shuffle()函数。洗牌算法由Ronald A.Fisher和Frank Yates于1983年发明，思路是每次从未处理的数据中随机取出一个数字，然后把该数字放在数组中所有未处理数据的尾部。

第三种解决方案，既然数组重复排序的情况如此常见，那么我们可以先对数组做个判断，如果已经有序则直接返回，如果是逆序则直接倒序即可。

归并排序

约翰冯诺伊曼在1954年提出了归并排序。在讲到归并排序之前，首先思考一个问题：如何将两个有序的列表合并成一个有序的列表。

将两个有序的列表合并成一个有序的列表

最简单的思路是，将两个列表拼接成一个列表，然后使用排序算法。觉得太暴力，那换个思路。

开辟一个长度等同于两个数组长度之和的新数组，并使用两个指针来遍历原有的两个数组，不断将较小的数字添加到新数组中，并移动对应的指针即可。

根据这个思路我们可以写出两个有序列表的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static int[] merge(int[] nums1, int[] nums2){
    //创建一个新数组用于存储结果
    int[] res = new int[nums1.length + nums2.length];
    //创建两个指针指向两个数组的首位
    int i = 0, j = 0;
    while(i < nums1.length && j < nums2.length){
        if(nums[i] < nums[j]){
            res[i+j] = nums[i++];
        }else{
            res[i+j] = nums[j++];
        }
    }
    
    //将剩余的数字补上
    while(i < nums1.length){
        res[i+j] = nums[i++];
    }
    while(j < nums2.length){
        res[i+j] = nums[j++];
    }
    
    return res;
}

合并有序数组的问题解决了，但我们排序时用的都是无序数组，那么上哪里去找这两个有序的数组呢？

我们可以把数组不断地拆成两份，直到剩下一个数字时，这个数字组成的数组我们就可以认为它是有序的。

然后通过上述合并有序列表的思路，将1个数字组成的有序数组合并成一个包含2个数字的有序数组，再将2个数字组成的有序数组合并成包含4个数字的有序数组，直到整个数组排序完成，这就是归并排序(Merge Sort)的思想。

将数组拆分成有序数组

拆分过程使用了二分思想，这是一个递归的过程，归并排序使用的递归框架如下：

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
46
47
48
49
public static void mergeSort(int[] nums){
    if(nums == null || num.length == 0){
        return;
    }
    mergetSort(nums, 0, nums.length-1);
}

private static void mergeSort(int[] nums, int lo, int hi){
    //递归的边界条件
    if(lo >= hi){
        return;
    }
    int mid = ((hi - lo) >> 1) + lo;
    //拆分左边区域
    mergeSort(nums, lo, mid);
    //拆分右边区域
    mergeSort(nums, mid+1, hi);
    //添加一个判断若左边的最大值小于右边的最小值，则不需要合并
    if(nums[mid] < nums[mid+1]){
        return;
    }
    //合并左右区域
    merge(nums, lo, mid, hi);
}

private static void merge(int[] nums, int lo, int mid, int hi){
    //定义三个指针用于合并数组
    int i = lo, j = mid+1, k = 0;
    //构建一个辅助数组用于存储合并完的结果
    int[] temp = new int[hi - lo + 1];
    
    //合并的思路
    while(i <= mid && j <= hi){
        temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
    }
    
    while(i <= mid){
        temp[k++] = nums[i++];
    }
    
    while(j <= hi){
        temp[k++] = nums[j++];
    }
    
    //将合并的数组修改到原数组中
    for(int index = 0; index < temp.length; index++){
        nums[lo + index] = temp[index];
    }
}

时间复杂度和空间复杂度

归并排序的复杂度比较容易分析，拆分数组的过程中，会将数组拆分$logn$次，每层执行的比较次数都约等于n次，所以时间复杂度为：$O(nlogn)$。空间复杂度是：$O(n)$​，主要占用空间的就是我们在排序前创建的长度为n的result数组。

分析归并可知，归并排序是一种稳定的排序算法。

总结起来，归并排序分成两步，一是拆分数组，二是合并数组，它是分治思想的典型应用。分治的思想是“分而治之”，分的时候体现了二分的思想，治是一个滚雪球的过程，将一个数字组成的有序数组合并成一个包含2个数字的有序数组，再将2个数字组成的有序数组合并成4个数字的有序数组。

由于性能较好，且排序稳定，归并排序应用非常广泛，Arrays.sort()源码中的TimSort就是归并排序的优化版。

合并排序的数组

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

1
2
3
4
5
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        //定义三个指针
        int i = m-1, j = n-1, k = m+n-1;
        //归并的思路倒序
        while(i >= 0 && j >= 0){
            A[k--] = A[i] > B[j] ? A[i--] : B[j--];
        }

        while(j >= 0){
            A[k--] = B[j--];
        }
    }
}

数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

1
2
输入: [7,5,6,4]
输出: 5
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    private int count = 0;

    public int reversePairs(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }

        mergeSort(nums, 0, nums.length - 1);

        return count;
    }

    private void mergeSort(int[] nums, int lo, int hi) {
        if(lo >= hi) {
            return;
        }

        int mid = ((hi - lo) >> 1) + lo;

        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        if(nums[mid] < nums[mid+1]){
            return;
        }
        merge(nums, lo, mid, hi);
    }

    private void merge(int[] nums, int lo, int mid, int hi) {
        int[] temp = new int[hi - lo + 1];
        int i = lo;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= hi) {
            if(nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                // 左右两个数组有序（升序排列）
                // 右边的数nums[j]小于左边的数nums[i]，也一定小于nums[i]之后的数
                // 与nums[j]组成逆序对的个数与nums[i]之后（包括nums[i]自己）的数的个数相同
                count += (mid - i + 1);
            }
        }

        while(i <= mid) {
            temp[k++] = nums[i++];
        }

        while(j <= hi) {
            temp[k++] = nums[j++];
        }

        //修改数组
        for(int index = 0; index < temp.length; index++){
            nums[lo + index] = temp[index];
        }
    }
}

时间复杂度$O(n)$级排序算法

计数排序

1959年7月，希尔排序通过交换相邻元素，打破了$O(n^{2})$的魔咒，使得排序算法复杂度降到了$O(nlogn)$级，此后的快速排序，堆排序都是基于这样的思想，所以它们的时间复杂度都是$O(nlogn)$。

那么，排序算法最好的时间复杂度就是$O(nlogn)$吗？是否有比$O(nlogn)$级还要快的排序算法呢？能否在$O(n)$​的时间复杂度下完成排序呢？

事实上，$O(n)$级的排序算法存在已久，但它们只能适用于特定的场景。

计数排序就是一种时间复杂度为$O(n)$的排序算法，该算法于1954年由Harold H.Seward提出。在对一定范围内的整数排序时，它的复杂度为$O(n+k)$(其中k是整数的范围大小。)

伪计数排序

若我们需要对一列数组排序，这个数组中每个元素都是[1,9]区间内的整数。我们可以构建一个长度为9的数组用于计数，计数数组的下标分别对应区间内的9个整数。然后遍历待排序的数组，将区间内每个整数出现的次数统计到计数数组中对应下标的位置。最后遍历计数数组，将每个元素输出，输出的次数就是对应位置记录的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void countSort(int[] nums){
    //建立长度为9的数组，下标为0~8，对应数字为1~9
    int[] temp = new int[9];
    for(int e : nums){
        temp[e-1]++;
    }
    int index = 0;
    for(int i = 0; i < 9; i++){
        while(temp[i] != 0){
            nums[index++] = i+1;
            temp[i]--;
        }
    }
}

算法非常简单，但这里的排序算法并不是真正的计数排序。因为现在的实现有一个非常大的弊端：排序完成后，nums中记录的元素已经不是最开始的那个元素了，它们只是值相等，但却不是同一个对象。

在纯数字排序中，这个弊端或许看起来无伤大雅，但在实际的工作中，这样的排序算法几乎无法使用。因为被排序的对象往往都会携带其他的属性，但这份算法将被排序对象的其他属性都丢失了。

伪计数排序2.0

对于这个问题，我们很容易想到另外一种解决方案：在统计元素出现的次数时，同时把真实的元素保存到列表中，输出时，从列表中取真实的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void countSort(int[] nums){
    //建立长度为9的数组，下标为0~8，对应数字为1~9
    int[] temp = new int[9];
    //创建一个Map用于记录下标中包含的真实元素
    HashMap<Integer, Queue<Integer>> records = new HashMap<>();
    for(int e : nums){
        //将每个整数出现的次数统计到计数数组中对应的下标的位置
        temp[e - 1]++;
        if(!records.containsKey(e-1)){
            records.put(e-1, new LinkedList<>());
        }
        records.get(e-1).add(e);
    }
    int index = 0;
    for(int i = 0; i < 9; i++){
        while(temp[i] != 0){
            //输出记录的真实元素
            nums[index++] = records.get(i).remove();
            temp[i]--;
        }
    }
}

通过队列来保存真实的元素，计数完成后，将队列中真实的元素赋值到nums列表中，这就解决了信息丢失的问题，并且使用队列还可以保证排序算法的稳定性。

但是这也不是真正的计数排序，计数排序中使用了一种更巧妙的方法解决这个问题。

真正的计数排序

计数排序并不是把计数数组的下标直接作为结果输出，而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置。

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
public static void countSort(int[] nums){
    //建立长度为9的数组，下标为0~8，对应数字为1~9
    int[] temp = new int[9];
    // 遍历 nums 中的每个元素
    for(int e : nums){
        temp[e-1]++;
    }
    
    //记录前面比自己小的数字的总数
    int preCount = 0;
    for(int i = 0; i < temp.length; i++){
        int cur = temp[i];
        //将temp计算成当前数字在结果中的起始下标位置。位置=前面比自己小的数字的总数
        temp[i] = preCount;
        //当前的数字比下一个数字小，累计到preCount中
        preCount += cur;
    }
    
    int[] result = new int[nums.length];
    for(int e : nums){
        //temp[e-1]表示此元素在结果数组中的下标
        int index = temp[e-1];
        result[index] = e;
        //跟新temp[e-1]，指向此元素的下一个下标
        temp[e-1]++;
    }
    
    //将结果赋值回nums
    for(int i = 0; i < nums.length; i++){
        nums[i] = result[i];
    }
}

首先我们将每位元素出现的次数记录到temp数组中。然后将temp[i]跟新为数字i在最终排序结果中的起始下标位置。这个位置等于前面比自己小的数字的总数。

接下来从头访问nums数组，根据temp中计算出下标位置，将nums的每个元素直接放到最终位置上，然后跟新temp中的下标位置。

时间复杂度和空间复杂度

从计数排序的实现代码中，可以看到，每次遍历都是进行n次或者k次，所以计数排序的时间复杂度为$O(n+k)$，k表示数据的范围大小。

用到空间主要是长度为k的计数数组的和长度为n的结果数组，所以空间复杂度也是$O(n+k)$。

需要注意的是，一般分析时间复杂度和空间复杂度时，常数项都是忽略不计的。但计数排序的常数项可能非常大，以至于我们无法忽略。

计数排序存在一个非常大的隐患，例如我们想要对这个数组排序：

1
int[] nums = new int[]{1, Integer.MAX_VALUES};

尽管它只包含两个元素，但是数据范围是$[1,2^{31}]$​，我们知道java中int占用4个字节，一个长度为$2^{31}$次方的int数组大约占用8G的空间。如果使用计数排序，仅仅排序这两个元素，声明计数数组就会占用超大的内存，甚至导致OOM异常。

所以计数排序只适用于数据范围不大的场景。例如对考试成绩排序就非常适合计数排序，如果需要排序的数字中存在一位小数，可以将所有数字乘以10，再去计算最终的下标位置。

数组的相对排序

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

1
2
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
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
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //找出arr1中最大的数字
        int max = -1;
        for(int e : arr1){
            if(e > max){
                max = e;
            }
        }

        //构建一个数组用于计数
        int[] temp = new int[max+1];

        //计数
        for(int e : arr1){
            temp[e]++;
        }

        //创建一个数组用于保存结果
        int[] res = new int[arr1.length];
        int index = 0;
        //先将数组2中的数字排序
        for(int e : arr2){
            for(int i = 0; i < temp[e]; i++){
                res[index++] = e;
            }
            temp[e] = 0;
        }

        //再将数组2中未出现的数字排序
        for(int i = 0; i <= max; i++){
            for(int j = 0; j < temp[i]; j++){
                res[index++] = i;
            }
        }

        return res;
    }
}
Donate comment here