前言

冒泡,插入,选择这三种基础的排序算法,比较简单效率不高,工作中一般不会使用,但是当做算法来研究还是能了解一些知识的,本文以<数据结构与算法之美>为基础,详细解析一下.

正文

首先要引入几个概念

稳定性

如果待排序数组中有相同的元素,排序过后它们的相对顺序不发生变化. 比如 2，9，3，4，8，3 排序过后为2, 3 , 3, 4, 8, 9 这两个3的相对顺序不变.这样就是具有稳定性. 稳定性可以保证复杂数据结构排序时的相对有序性. 比如我们要对一笔订单先按金额排列,金额相同的再按时间排序
就可以先将这笔订单按照时间排序,再采用具有稳定性的排序算法按金额进行排序. 猜测Java8中的compare().thenCompare()就是采用这种原理实现

原地排序

排序过程中只占用常数级的额外空间或者不占用额外空间

有序度

数组中具有有序关系的元素对的个数,数学表达式为 有序元素对：a[i] <= a[j], 如果i < j。
2,4,3,1,5,6 的有序度为11,有序元素对为(2,4),(2,3),(2,5),(2,6),(4,5),(4,6),(3,5),(3,6),(1,5),(1,6),(5,6)
对 6,5,4,3,2,1 这个完全逆序的数组,有序度为0
对 1,2,3,4,5,6 这个完全有序的数组,有序度为(n-1)+(n-2)+(n-3)+...+0 = n*(n-1)/2 = 15,即满有序度

逆序度

和有序度定义正好相反 逆序度 = 满有序度 - 有序度

约定

为了方便描述,这里约定数组为arr[0~n],n≥1,排列方式为正序(从小到大).
下面的描述不会举例讲解,推荐到 visualgo查看动画演示

冒泡排序

主要思路

首先将数组在逻辑划分为左侧的未排序部分和右侧的已排序部分
冒泡排序中对未排序部分的一次遍历称为一次冒泡,初始时未排序部分为arr[0~n-1],未排序部分为空.冒泡一次后,未排序部分为arr[0~n-2],已排序部分为arr[n-1~n-1],冒泡x(1≤x<n)次后,未排序部分为arr[0~n-1-x),已排序部分为arr[n-x~n-1],最终达成全部排序
每次冒泡未排序部分时,只会操作相邻的元素,方向为 arr[0]→ arr[n-1],如果a[i]>a[i+1]就进行交换,这样一次冒泡操作后,未排序部分中的最大值就会移动到已排序部分且在最左侧(即已排序部分的最小值).
同时,如果一次冒泡后没有进行过任何交换说明整个数组已经有序了,结合这个特性可以省去不必要的冒泡,核心代码如下

public void sort(Comparable[] a) {
        if (a.length <= 1) {
            return;
        }
        for (int i = a.length - 1; i > 0; i--) {
            boolean changeFlag = false;
            for (int j = 0; j < i; j++) {
                if (a[j + 1].compareTo(a[j]) < 0) {
                    swap(a, j + 1, j);
                    changeFlag = true;
                }
            }
            if (!changeFlag) {
                break;
            }
        }
    }

时间复杂度

最坏情况下,数组完全倒序, 时间复杂度为 (n-1)+(n-2)+(n-3)+...+1 = (n^2)/2 ~= O(n^2) 数字表示交换的次数
最好情况下,数组已经有序,只需要一次冒泡, 时间复杂度为 O(n) 这里不会有交换,以比较的次数作为计量单位
平均情况下,用概率推算会很困难,这里采用上面提到的有序度和逆序度,并将元素的交换次数当做计量单位, 观察可以看到,每交换一次,都会使原来逆序的一组元素变为有序,逆序度即为交换次数,那么在最好情况下逆序度为0,最坏情况下逆序度为n(n-1)/2,平均时间复杂度为两者取平均值
(0 + n(n-1)/2)/2 = O(n^2)

是原地排序吗?

冒泡排序涉及到两个元素的交换,交换时只使用了一个单位临时空间,是原地排序

稳定吗?

冒泡排序中元素位置发生变化交换时,并且交换仅在a[i]>a[i+1]时才发生,a[i]==a[i+1]时时不会发生的,因此是稳定的

插入排序

主要思路

将数组分为左侧的已排序部分和右侧的未排序部分
初始时已排序部分为arr[0~0],未排序部分为arr[1~n-1]一次插入后,已排序部分为arr[0~1],未排序部分为arr[2~n-1],x(1≤x<n)次插入后,已排序部分为arr[0_{x],未排序部分为arr(x+1}n-1]
从未排序部分的起始位置开始(即arr[1]),每次插入时,方向为 arr[n-1]→ arr[0],找出第一个小于等于arr[i]的元素,有两种情况

1. 找到了,插入在它之后(具体实现时 假设找到的下标为j, 将a[j+1~i-1]的元素依次后移,再将a[i]设置到a[j+1]),
2. 没找到,说明a[i]就是当前最小的元素,将a[0~i-1]的元素依次后移,将a[i]设置到a[0]
   核心代码如下

public void sort(Comparable[] arr) {
            if (arr.length <= 1) {
                return;
            }
            for (int i = 1; i < arr.length; i++) {
                Comparable insertValue = arr[i];
                int insertPos = i;
                for (int j = i - 1; j >= 0; j--) {
                    if (insertValue.compareTo(arr[j]) < 0) {
                        arr[j + 1] = arr[j];
                        insertPos = j;
                    } else {
                        insertPos = j + 1;
                        break;
                    }
                }
                arr[insertPos] = insertValue;
            }
        }

时间复杂度

以元素移动的次数作为计量单位
最坏情况下,数组完全倒序,时间复杂度为 0 + 1 + 2 + 3 +...+ (n-1) = n*(n-1)/2 ~= O(n^2)
最好情况下,数组完全顺序, 时间复杂度为 1 + 1 + 1 + ... + 1= n ~=O(n)
平均情况下, 我们仍然使用逆序数这个概念,再观察依旧可以得知: 逆序数等于移动次数,所以时间复杂度为 (0 + n(n-1)/2)/2 ~= O(n^2)

是原地排序吗?

插入排序中,没有使用额外的空间,因此是原地排序

稳定吗

插入排序中,只有移动操作会改变元素位置,而判定条件是小于等于arr[i] ,符合情况1,a[i]会被设置到a[j+1],从而保证相对顺序的稳定.

选择排序

主要思路

将数组分为左侧的已排序部分和右侧的未排序部分
选择排序中选择表示对未排序部分的一次遍历,初始时已排序部分为空,未排序部分为arr[0~n-1],
一次选择后,已排序部分为arr[0~0],未排序部分为arr[1~n-1],x(1≤x<n)次选择后,已排序部分为arr[0~x-1],未排序部分为arr(x~n-1]
第x(1≤x<n)次选择时,找出未排序数组中的最小值,放入已排序数组(与arr[x-1]交换),核心代码如下

public void sort(Comparable[] arr) {
            if (arr.length <= 1) {
                return;
            }
            for (int i = 1; i < arr.length ; i++){
                int minPos=i-1;
                Comparable minValue=arr[i-1];
                for(int j=i;j<arr.length;j++){
                    if (minValue.compareTo(arr[j])>0){
                        minPos=j;
                        minValue=arr[j];
                    }
                }
                swap(arr,minPos,i-1);
            }
        }

时间复杂度

以minValue被替换的次数作为计量单位.
最坏情况下为 (n-1) + (n-2) + ... + 0 =n(n-1)/2 ~= O(n^2)
最好情况下为 1+1+1...+1 =n ~= O(n)
平均情况下,仍然使用逆序数, 可以发现: 逆序数等于替换的次数,因此时间复杂度为(0 + n(n-1)/2)/2 ~= O(n^2)

是原地排序吗?

选择排序中,minValue使用了一个单位的额外空间,因此是原地排序

稳定吗

选择排序中,没有约束可以确保稳定, 比如 4, 3, 2, 4, 1 排序过后,两个4的相对位置会发生变化

冒泡,插入,选择的比较

三者的相同之处

• 将数组虚拟为已排序和未排序部分,在排序过程中逐步将未排序部分转化为已排序部分.
• 都是原地排序
• 平均时间复杂度都是O(n^2)

三者的不同之处

• 冒泡排序,插入排序是稳定的,选择排序时不稳定的
• 冒泡和选择频繁使用交换操作,插入排序较多使用赋值操作,而赋值相比交换性能更好
  三者比较,根据我这里的简单测试 性能方面 选择>插入>冒泡, 但是选择排序不稳定,仅此一点很多场景下就不适用,实用性大大降低. 因此插入排序时三者中较好的选择.

总结

冒泡,插入,选择是三种基本的排序算法,研究他们对学习更高效的排序算法有帮助,相关源码已经上传到这里