排序算法系列

概述


概念
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序

反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序

 

 

排序分类

如果按照策略来分类,大致可分为:交换排序、插入排序、选择排序、归并排序和基数排序。如 图-排序策略分类图 所示。

排序算法系列
图-排序策略分类图

 

 

 

 

算法分析

下表给出各种排序的基本性能,具体分析请参看各排序的详解。

 
排序类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性
平均情况 最坏情况 最好情况
交换排序 冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 较复杂
插入排序 直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
希尔排序 O(nlog2n) O(n1.5)
O(1) 不稳定 较复杂
选择排序 简单选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
归并排序 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂

 

 本文转自静默虚空博客园博客,原文链接:http://www.cnblogs.com/jingmoxukong/p/3790604.html,如需转载请自行联系原作者

上一篇:Vue路由query 和 params 传参的区别


下一篇:阿里云java开发手册为什么规定只要重写 equals,就必须重写 hashCode?