11|排序（上）

2019-03-10 本文已影响0人攻城虱小马褂

如何分析一个排序算法

执行效率

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）插入排序具有一个赋值语句

对于同样逆序度的排序数据，插入排序更优于冒泡排序。