排序(上)

Wednesday, April 17, 2019

如何分析一个排序算法

执行效率

  • 最好情况,最坏情况,平均情况的时间复杂度
  • 时间复杂度的系数,常数,低阶 实际开发中,对比的可能是100,1000个这样规模的数据,所以在对比同一等级的时间复杂度的排序算法时,要把这几样考虑进来。
  • 比较次数和交换次数

排序算法的内存消耗

  • 原地排序,指空间复杂度为O(1)的排序算法

排序的稳定性

  • 如果待排序的序列中存在值相等的元素,经过排序后,相等元素之间原有的先后顺序不变。

比如我们要给订单系统排序,一个是订单时间,一个是订单金额,按照订单金额排序,如果一样,则按订单时间排序。

借助稳定排序算法,就可以对订单排两次序,先对订单时间排序,再对金额排序,这样第二次排序的时候,金额相等的订单就不会被打乱顺序。

file

冒泡排序

file

file

代码实现

特性

  • 冒泡排序是原地排序
  • 冒泡排序是稳定的排序算法(相等的元素不做交换)
  • 最好时间复杂度是O(n),最坏是O(n^2)

分析平均时间复杂度

通过有序度和逆序度这两个概念来分析

  • 有序度是数组中具有有序关系的元素对个数

file

  • 倒序排列的数组,有序度是0,完全有序的数组的有序度是 n * (n -1) / 2,也叫满有序度
  • 逆序度 = 满有序度- 有序度
  • 冒泡排序就是比较和交换,每交换一次,有序度就加1,交换次数是确定的,即为逆序度。
  • 做好的情况下就是满有序度,不需要交换,即 n _ (n - 1) / 2,取个中间值即 n _ (n - 1) / 4,也就是平均情况下要进行的交换操作次数,但是比较次数相比交换次数会多得多,复杂度的上限是O(n^2),所以平均时间复杂度也是O(n^2)

插入排序

file

  • 对于一个给定的初始序列, 移动操作的次数是固定的,等于逆序度

file

代码实现

特性

  • 插入排序是原地算法
  • 插入排序是稳定算法(对于值相同的元素,将后面出现的元素插入到前面元素的后面)
  • 最好时间复杂度是O(n),最坏和平均时间复杂度是O(n^2)

选择排序

  • 选择排序每次会从未排序区间找到最小的元素,将其放到已排序区间的末尾。

file

数据结构-算法

排序(下)

队列(下)