常见排序算法的稳定性分析

稳定性简而言之就是带相同元素在排序前和排序后的相对位置是否保持一致。

默认从小到大的进行排序

1.冒泡排序

思想:每一轮都是将最大的一个元素冒到数组的结尾。

分析:当相邻的两个元素相等的时候,通常的做法应该是选择后面的那个相同元素继续做冒泡的比较,这样稳定性就不会被破坏。但是如果你在两个相邻元素相同的时,还是选择了交换两个相同的元素,这样稳定性就会遭到破坏,当然没有人会这么多此一举,所以通常默认情况下,因此冒泡排序就是一个稳定的排序算法。

2.选择排序

思想:每一轮选择最小的值所在的下边,确定之后交换到特定位置

分析:举个反例 5,4,5,3 排序,第一轮之后 3,4,5,5 。两个5的相对位置发生了变化,因此选择排序不稳定

3.插入排序

思想:维护数组前部分有序,当前元素插入到合适的位置。

分析:如果再向前找的过程中发现相同元素,则插再这个相同元素的后面,这样相同元素的相对位置不发生变化,是一种稳定的排序算法。但是如果你找到相同元素的时候,硬是要插入到前面,那么就是不稳定了,这里的稳定是默认你不会做这么无聊的操作了。

4.快速排序

思想:主元+分治

分析:举一个反例:3,2,2 第一轮3作为主元,变成 2,2,3 ,这样就可以认为排好序了。两个2的相对位置发生了变化,一种不稳定的排序算法。

5.归并排序

思想:分治与归并

分析:元素的交换只发生的归并的阶段,就是merge两个有序的小数组的过程。归并的过程中需要借助辅助数组。两个有序数组中,小的数排前面,当遇到相同的数的时候,则左边数组的数先排,这样就可以保持相对位置。因此是一种稳定的算法。如果你非要先排右边数组的元素,那么就破坏了稳定性,当然也是需要考虑到你不会这么做。

其他排序算法:

桶排序(基数、计数):稳定

堆、希尔:不稳定

上述提到的稳定算法基本上都是理想上可以达到的,当程序员的实现上不严谨的时候,会导致稳定的排序算法变成一种不稳定的排序算法。

工程中的排序算法

工程中类库提供的排序都是经过高度集成与优化的,时间复杂度O(NlogN)的算法都涉及到递归的操作,工程中是不允许出现递归,递归排序都被改写成了非递归的。

Java中的Arrays.sort方法会先判断数据的长度,如果数据在一定范围内,会直接使用插入排序,因为插入排序虽然是一个时间复杂为O(N²)的排序算法,但是如果数据量并不是很大,那么相对来讲很快,并且插入排序的特点就是如果一个数据近似有序,那么时间复杂度也近似O(N)。如果数据量较大,那么Arrays.sort方法会再判断排序的data是基础类型还是一个自己定义的对象,如果是基础类型,那么会使用快排,因为基础类型要保持稳定性是无意义的,如果是对象例如自己定义的类Student,那么就会使用归并排序,保证data的稳定性。无论是归并排序还是快速排序,当数据量被分解到一定范围时,会再次转换为插入排序 。

参考文献:

https://blog.csdn.net/wumenglu1018/article/details/106712801

https://www.jianshu.com/p/a5b5b5c4ee0f

彻底理解原码、反码和补码

本科时从计算机组成原理这门课程上学习计算机的编码方式,原码反码和补码,始终是很混乱,也可以说学了就忘忘了再看看了又忘,。从网上的一些博客也好,也很难找到一种特别具象化形象的理解方式,因此本人制作了一个较为具象化的视频来讲解原码反码和补码的区别以及计算机为什么最终采用补码作为编码方式。视频如下:

https://www.bilibili.com/video/BV1Yk4y1r7D4/