1. 冒泡排序

1.1 原理

冒泡排序原理

通过遍历所有元素,判断相邻的两个元素是否满足大小关系,如果不满足则进行交换,重复 n 次,就完成 n 个数据的排序工作。

1.2 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    public static void bubbleSort(int[] nums) {
        if (nums.length <= 1) return;
        for (int i = 0; i < nums.length; i++) {
            // 从小到大排序
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }

对于上述的代码存在一种优化方式,如果当某次的冒泡排序没有数据交换的时候,说明已经达到了完全有序,则可以直接完成排序,优化后的代码如下。

1.3 优化后的代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    public static void bubbleSort(int[] nums) {
        if (nums.length <= 1) return;
        for (int i = 0; i < nums.length; i++) {
            // 增加一个标志位
            boolean flag = true;
            for (int j = 0; j < nums.length - i - 1; j++) {
                // 从小到大排序
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    flag = false;
                }
            }
            // 一轮冒泡完之后,如果 flag 没有改变说明没有发生交换
            // 则直接结束冒泡
            if (flag) break;
        }
    }

1.4 空间复杂度、时间复杂度与稳定性

空间复杂度 最好时间复杂度 最坏时间复杂度 平均时间复杂度 是否稳定排序算法
O(1) O(n) O(\(n^2\)) O(\(n^2\))

1.5 平均时间复杂度的分析过程

有序元素为:a[i]<=a[j], i<j。逆序元素为:a[i]>a[j], i<j。分析过程仅考虑元素从小到大的排列方式。

冒泡排序包含两个操作原子,比较和交换。每交换一次,有序度就加一。不管算法怎么改进,交换次数总是确定的,即为逆序度,也就是 \(n*(n-1)/2 - 初始有序度\)。(逆序度 = 满有序度 - 初始有序度)

在最坏情况下,初始有序度是 0,所以逆序度为 \(n*(n-1)/2\)。在最好情况下,初始有序度为 \(n*(n-1)/2\),逆序度为 0。取个平均值 \(n*(n-1)/4\),总共平均需要 \(n*(n-1)/4\) 次交换,由于比较操作比交换操作多,而最坏时间复杂度为 O(\(n^2\)),所以根据夹逼法则就能推出来平均时间复杂度为 O(\(n^2\))。

这种方式不是很严谨,但是比较实用,比概率论的计算方式简单。

2. 插入排序

2.1 原理

插入排序原理图

首先,将数据分为两个区间,已排序区间和未排序区间,初始已排序区间只有一个元素,就是第一个元素,然后取未排序中的元素,在已排序区间中找到合适的插入位置将其插入,重复这个过程直到未排序区间中的元素为空,算法结束。

2.2 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    public static void insertSort(int[] nums) {
        if (nums.length <= 1) return;
        // 从第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 取出遍历到的这个元素的值保存起来
            int value = nums[i];
            // 计算出有序区间的最后一个数的下标
            int j = i - 1;
            // 从后向前遍历整个有序区间
            for (; j >= 0; j--) {
                if (nums[j] > value) {
                    // 如果有序区间的数比待插入的数字大
                    // 则将其向后移动一位
                    nums[j + 1] = nums[j];
                } else {
                    // 如果有序区间的数小于等于待插入的数
                    // 则跳出循环,将数字插入这个数字前面的位置
                    break;
                }
            }
            // 插入数字
            nums[j + 1] = value;
        }
    }

2.3 空间复杂度、时间复杂度与稳定性

空间复杂度 最好时间复杂度 最坏时间复杂度 平均时间复杂度 是否稳定排序算法
O(1) O(n) O(\(n^2\)) O(\(n^2\))

2.4 平均时间复杂度的分析过程

在数组中平均插入一个数据的平均时间复杂度是 O(n),对于插入排序来说,每次插入操作相当于在数组中插入一个数据,循环执行 n 次插入操作,所以平均时间复杂度为 O(\(n^2\))

3. 选择排序

3.1 原理

选择排序的原理

选择排序算法的实现思路类似插入排序,也分为已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

3.2 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    public static void selectSort(int[] nums) {
        if (nums.length <= 1) return;
        // 遍历数组中的所有元素
        for (int i = 0; i < nums.length; i++) {
            // 保存最小数的数组下标
            // 初始化的时候保存未排序区间的第一个值
            int low = i;
            // 遍历未排序区间
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[low] > nums[j]) {
                    // 如果下标表示的最小值比遍历到的值大
                    // 则将最小值下标替换为 j
                    low = j;
                }
            }
            int tmp = nums[i];
            nums[i] = nums[low];
            nums[low] = tmp;
        }
    }

3.3 空间复杂度、时间复杂度与稳定性

空间复杂度 最好时间复杂度 最坏时间复杂度 平均时间复杂度 是否稳定排序算法
O(1) O(\(n^2\)) O(\(n^2\)) O(\(n^2\))

4. 为什么插入排序比冒泡排序快

虽然从空间复杂度、时间复杂度与稳定性上来看插入排序和冒泡排序的指标都一样,但是由于冒泡排序需要进行的交换操作比插入操作多很多,所以在数据量大的时候,插入排序的速度比冒泡排序快很多。以下为测试代码

 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
60
61
62
public class Main {
    public static void main(String[] args) {
        int[] num1 = new int[100000];
        for (int i = 0; i < num1.length; i++) {
            num1[i] = (int) (Math.random() * 10);
        }
        int[] num2 = num1.clone();
        long startTime1 = System.currentTimeMillis();
        insertSort(num1);
        long endTime1 = System.currentTimeMillis();
        System.out.println("The insert sort consume time is [" + (endTime1 - startTime1) + "ms]");
        long startTime2 = System.currentTimeMillis();
        bubbleSort(num2);
        long endTime2 = System.currentTimeMillis();
        System.out.println("The bubble sort consume time is [" + (endTime2 - startTime2) + "ms]");
    }

    public static void insertSort(int[] nums) {
        if (nums.length <= 1) return;
        // 从第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 取出遍历到的这个元素的值保存起来
            int value = nums[i];
            // 计算出有序区间的最后一个数的下标
            int j = i - 1;
            // 从后向前遍历整个有序区间
            for (; j >= 0; j--) {
                if (nums[j] > value) {
                    // 如果有序区间的数比待插入的数字大
                    // 则将其向后移动一位
                    nums[j + 1] = nums[j];
                } else {
                    // 如果有序区间的数小于等于待插入的数
                    // 则跳出循环,将数字插入这个数字前面的位置
                    break;
                }
            }
            // 插入数字
            nums[j + 1] = value;
        }
    }

    public static void bubbleSort(int[] nums) {
        if (nums.length <= 1) return;
        for (int i = 0; i < nums.length; i++) {
            // 增加一个标志位
            boolean flag = true;
            for (int j = 0; j < nums.length - i - 1; j++) {
                // 从小到大排序
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    flag = false;
                }
            }
            // 一轮冒泡完之后,如果 flag 没有改变说明没有发生交换
            // 则直接结束冒泡
            if (flag) break;
        }
    }
}

测试结果

1
2
The insert sort consume time is [1535ms]
The bubble sort consume time is [18039ms]