今天我们来说说这三个经典的排序，先说一下结论：插入排序最好。
今天讲的这三种排序都是适用于小规模排序的，相对而言是高效的，之后我再介绍大规模排序的适用算法!
首先我们来看看插入排序。
插入排序的思路就是将你要排序的数组分两个区间，一个是已排序区间，一个是未排序区间，初始的时候默认第一个元素是已排序区间的，后面的所有元素为未排序区间。然后呢依次取未排序区间的元素，在已排序区间找到合适的位置插入。直到未排序区间空了。
注意我们这里的分区间只是我们主观分法，实际上物理空间还是一个数组的，没有分为两个数组。来看下代码
image
从代码我们可以看出，插入排序是原地排序，不需要额外的空间！而且是稳定排序的算法，时间的复杂度最好为O(n),最坏为O(n2),平均为O(n2)。
再来看看冒泡排序。
冒泡排序的思路就是相邻的两个数据进行比较，需要交换就交换一下，每一次冒泡都会至少让一个元素放到正确的位置，最多重复了N次，排序结束。
还是上面那个数组[3,2,5,1,4]。
这样冒泡下去直到全部有序！以下是代码。
从代码我们可以看出，冒泡排序是原地排序，不需要额外的空间！而且是稳定排序的算法，时间的复杂度最好为O(n),最坏为O(n2),平均为O(n2)。
最后来看看选择排序
选择排序也是分两个区间，已排序区间和未排序区间，每次从未排序区间里面选择最小的放入已排序区间尾部。
再来看一下代码
从代码我们可以看出，选择排序是原地排序，不需要额外的空间！但是是不稳定排序的算法！时间的复杂度最好,最坏为,平均都为O(n2)。
比如数组A[3,4,3,2]。第一次找到最小的2和3换了一下，那第一个3和第二个3位置顺序就变化了所以不稳定了！
所以从时间复杂度和稳定的角度来说，冒泡和插入排序比选择排序好！
那插入排序为什么比冒泡排序好呢？
对比两种算法的核心比较代码，冒泡需要3个赋值，而排序只要一个赋值，我们知道每一个语句执行是有时间的，所以冒泡的总耗时会比插入多！
所以插入排序更好！
建议大家看了之后自己代码实现以下，加深记忆！
如果错误欢迎指正！
网友评论