排序算法
#算法 2022-07-09

排序算法是算法的入门知识，其经典思想可以用于很多算法当中。

工具函数

交换函数

1
2
3
4
5
public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

十大经典排序算法

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡 \(O(n^2)\) \(O(n)\) \(O(n^2)\) \(O(1)\) 稳定
选择 \(O(n^2)\) \(O(n)\) \(O(n^2)\) \(O(1)\) 不稳定
插入 \(O(n^2)\) \(O(n)\) \(O(n^2)\) \(O(1)\) 稳定
希尔 \(O(n\log n)\) \(O(n\log^2n)\) \(O(n\log^2n)\) \(O(1)\) 不稳定
归并 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(n)\) 稳定
快速 \(O(n\log n)\) \(O(n\log n)\) \(O(n^2)\) \(O(\log n)\) 不稳定
堆 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(1)\) 不稳定
计数 \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) \(O(k)\) 稳定
桶 \(O(n+k)\) \(O(n+k)\) \(O(n^2)\) \(O(n+k)\) 稳定
基数 \(O(nk)\) \(O(nk)\) \(O(nk)\) \(O(n+k)\) 稳定

冒泡排序

冒泡排序要对一个列表多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对 列表实行一次遍历，就有一个最大项排在了正确的位置。

普通版：

1
2
3
4
5
6
7
8
9
public void bubbleSort(int[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (nums[j] > nums[j + 1])
                swap(nums, j, j + 1);
        }
    }
}

如果发现列表已经排好序了，那么就可以提前结束。

优化版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void bubbleSort(int[] nums) {
    int n = nums.length;
    boolean flag = false;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                flag = true;
            }
        }
        if (!flag) 
            break;
    }
}

参考资料