如何分析一个排序算法
执行效率
1. 最好情况、最坏情况、平均情况时间复杂度
2. 时间复杂度的系数、常数、低阶
3. 比较次数和交换（移动）次数
内存消耗
通过空间复杂度来衡量，原地排序指的是空间复杂度为o(1)的排序算法
稳定性
如果待排序的序列中存在值相等的元素，经过排序后，相等元素间的先后顺序不变
三种时间复杂度为o(n^2)的排序
冒泡排序
（1）操作相邻的两个数据
（2）一次冒泡至少让一个元素移动到应该在的位置
分析：
（1）原地排序：冒泡只涉及相邻数据交换，只需要常量级的临时空间，空间复杂度O(1), 是原地排序
（2）稳定排序：当相邻的两个元素大小相等的时候不作交换，所以相同大小的数据在排序前后不会改变顺序，所以是稳定排序。
（3）时间复杂度
a. 最好情况：排序数据已经有序，只需要进行一次冒泡操作，时间复杂度O(n)
b.最坏情况：排序数据刚好倒序排列，需要进行n此冒泡操作，时间复杂度O(n^2)
c. 平均情况：利用有序度和逆序度来衡量。 满有序度为n*(n-1)/2
逆序度 = 满有序度 - 有序度
最坏情况，有序度为0，要进行n*(n-1)/2 次比较交换， 平均情况取n*(n-1)/4 所以平均情况下 时间复杂度也是O(n^2)
插入排序(动态的往有序区间添加数据)
如何实现：
（1）划分两个区间，已排序区间和未排序区间
（2）取未排序区间的元素，在已排序区间中找到合适的位置插入
（3）一直重复这个过程直到未排序区间中的元素为空
对于一个给定的初始序列，移动操作的次数是固定的，就等于逆序度
分析：
（1）原地排序：插入排序不需要额外的存储空间，空间复杂度O(1), 是原地排序
（2）稳定排序：对于值相等的元素，可以将后面出现的元素插入到前面痴线元素的后面，这样就保证的前后的顺序不会变，所以是稳定排序
（3）时间复杂度：
a. 最好情况：排序数据已经有序，只需从未到头遍历有序的数据，时间复杂度O(n)
b. 最坏情况： 排序数据倒序，每次插入相当于在数据的第一个位置插入新的数据，需要移动大量数据，时间复杂度O(n^2)
c. 平均情况： 数据插入一个元素的平均复杂度为O(n), 插入排序来说，每次插入就相当于在数据插入一个元素，所以插入排序平均情况时间复杂度O(n^2)
选择排序
选择排序
实现原理与插入排序类似， 区别就是选择排序每次会从未排序区间找到最小的元素，放到已经排序区间的末尾。
分析：
（1）原地排序， 选择排序不需要分配额外的存储空间，空间复杂度是O(1), 是原地排序
（2）稳定排序：选择排序每次都要找到剩余未排序的最小值与前面的元素进行交换，这样会破坏稳定性，如5，8，5，2，9这样的排序数据。
（3）时间复杂度：
a. 最好情况： 每一次交换都要找到最小的元素，要进行n次交换，所以最好情况时间复杂度为O(n^2)
b. 最坏情况：O(n^2)
c. 平均情况：O(n^2)
写在最后
为什么插入排序比冒泡排序更受欢迎
虽然冒泡排序和插入排序具有相同的时间复杂度，都是O(n^2), 但是冒泡排序的实现更加复杂，
从代码实现来看
（1）冒泡排序具有3个赋值语句
（2）插入排序具有一个赋值语句
对于同样逆序度的排序数据，插入排序更优于冒泡排序。
网友评论