排序算法

面向各种排序算法，

  • 基本：【冒泡(Bubble)，插入(Insertion)】;

  • 常用：【归并(Merge)，快速(Quick)，拓扑(Topological)】；

  • 其他：【堆(Heap)、桶(Bucket)】；

归并、快速、拓扑的思想是解决绝大部分排序问题的关键，堆和桶排序经常可以在线性时间复杂度内解决问题。

冒泡

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sort(int[] nums) {
    //定义一个布尔变量 hasChange，用来标记每轮遍历中是否发生了交换
    boolean hasChange = true; 

    //每轮遍历开始，将 hasChange 设置为 false
    for (int i = 0; i < nums.length - 1 && hasChange; i++) {
        hasChange = false;

        //进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生
        for (int j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                hasChange = true;
            }
        }
     }
 }

分析

空间复杂度

假设数组的元素个数是 n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。

时间复杂度

  1. 给定的数组按照顺序已经排好

    • 在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

  2. 给定的数组按照逆序排列

    • 在这种情况下，我们需要进行 n(n-1) / 2 次比较，时间复杂度是 O($n^2$)。这是最坏的情况。

  3. 给定的数组杂乱无章

    • 在这种情况下，平均时间复杂度是 O($n^2$)。

由此可见，冒泡排序的时间复杂度是 O($n^2$)。它是一种稳定的排序算法。（稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。）

插入

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sort(int[] nums) {
    // 将数组的第一个元素当作已经排好序的，从第二个元素，即 i 从 1 开始遍历数组
    for (int i = 1, j, current; i < nums.length; i++) {
        // 外围循环开始，把当前 i 指向的值用 current 保存
        current = nums[i];

        // 指针 j 内循环，和 current 值比较，若 j 所指向的值比 current 值大，则该数右移一位
        for (j = i - 1; j >= 0 && nums[j] > current; j--) {
            nums[j + 1] = nums[j];
            }
    
        // 内循环结束，j+1 所指向的位置就是 current 值插入的位置
        nums[j + 1] = current;
    }
}

分析

空间复杂度

假设数组的元素个数是 n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是 O(1)。

时间复杂度

  1. 给定的数组按照顺序已经排好

    • 只需要进行 n-1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

  2. 给定的数组按照逆序排列

    • 在这种情况下，我们需要进行 n(n-1) / 2 次比较，时间复杂度是 O($n^2$)。这是最坏的情况。

  3. 给定的数组杂乱无章

    • 在这种情况下，平均时间复杂度是 O($n^2$)。

    由此可见，和冒泡排序一样，插入排序的时间复杂度是 O($n^2$)，并且它也是一种稳定的排序算法。

E.g.: LeetCode 147 链表插入排序

归并

基本思想：分治

不断分组到很小的数组，然后进行排序合并

实现

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
void sort(int[] A, int lo, int hi) {
  // 判断是否只剩下最后一个元素
  if (lo >= hi) return;
  
  // 从中间将数组分成两个部分
  int mid = lo + (hi - lo) / 2;
  
  // 分别递归地将左右两半排好序
  sort(A, lo, mid);
  sort(A, mid + 1, hi);

  // 将排好序的左右两半合并  
  merge(A, lo, mid, hi);
}


//归并操作

void merge(int[] nums, int lo, int mid, int hi) {
    // 复制一份原来的数组
    int[] copy = nums.clone();
  
    // 定义一个 k 指针表示从什么位置开始修改原来的数组，i 指针表示左半边的起始位置，j 表示右半边的起始位置
    int k = lo, i = lo, j = mid + 1;
  
    while (k <= hi) {
        if (i > mid) {
            nums[k++] = copy[j++];
        } else if (j > hi) {
          nums[k++] = copy[i++];
        } else if (copy[j] < copy[i]) {
          nums[k++] = copy[j++];
        } else {
          nums[k++] = copy[i++];
        }
    }
}

分析

空间复杂度

由于合并 n 个元素需要分配一个大小为 n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。

时间复杂度

归并算法是一个不断递归的过程。

举例：数组的元素个数是 n，时间复杂度是 T(n) 的函数。

解法：把这个规模为 n 的问题分成两个规模分别为 n/2 的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有 n 个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式：T(n) = 2×T(n/2) + O(n)。

对于公式求解，不断地把一个规模为 n 的问题分解成规模为 n/2 的问题，一直分解到规模大小为 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。这里的次数是按照规模大小的变化分类的。

以此类推，对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。

快速排序

采用了分治的思想