基础排序算法—冒泡,插入,选择
- 2020 年 4 月 10 日
- 筆記
前言
冒泡,插入,选择这三种基础的排序算法,比较简单效率不高,工作中一般不会使用,但是当做算法来研究还是能了解一些知识的,本文以<数据结构与算法之美>为基础,详细解析一下.
正文
首先要引入几个概念
稳定性
如果待排序数组中有相同的元素,排序过后它们的相对顺序不发生变化. 比如 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[0x],未排序部分为arr(x+1n-1]
从未排序部分的起始位置开始(即arr[1]),每次插入时,方向为 arr[n-1]→ arr[0],找出第一个小于等于arr[i]的元素,有两种情况
- 找到了,插入在它之后(具体实现时 假设找到的下标为j, 将a[j+1~i-1]的元素依次后移,再将a[i]设置到a[j+1]),
- 没找到,说明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)
三者的不同之处
- 冒泡排序,插入排序是稳定的,选择排序时
不稳定的 - 冒泡和选择频繁使用交换操作,插入排序较多使用赋值操作,而赋值相比交换性能更好
三者比较,根据我这里的简单测试 性能方面选择>插入>冒泡, 但是选择排序不稳定,仅此一点很多场景下就不适用,实用性大大降低. 因此插入排序时三者中较好的选择.
总结
冒泡,插入,选择是三种基本的排序算法,研究他们对学习更高效的排序算法有帮助,相关源码已经上传到这里
