数据结构是程序的骨架,程序速度的好坏很大程度与数据结构骨架相关。为此做下总结,以备后查!
排序算法分很多种,其主要的有:1.冒泡排序,2.选择排序,3.插入排序,4.归并排序,5.希尔排序,6.快速排序,7.堆排序,8.计数排序,9.基数排序,10.桶排序等。
现在介绍两个概念:
排序稳定性:如果有若干数值相同,如{ a = 3, b = 7, c = 4, d = 3 },这里a和d的值相同。按升序排列是{ a, d, c, b};其中a应该排在d前面,即不打乱先前的顺序就为稳定排序。如果该算法具有这样的性质就称为排序稳定性。
原地排序:指不用申请多余的空间进行排序,就在原来的数据中比较和交换就可以完成排序。
现在介绍下排序负责度问题:
排序循环次数按由大到小为:(n为排序数目)n*n àn*log( n )àn.可以看出他们的变化趋势。
下面根据各自特性列出一张表单:
编号 |
排序法 |
平均时间 |
最差情况 |
稳定度 |
额外空间 |
备注 |
1 |
冒泡 |
O(n*n) |
O(n*n) |
稳定 |
O(1) |
n小时较好 |
2 |
选择 |
O(n*n) |
O(n*n) |
不稳定 |
O(1) |
n小时较好 |
3 |
插入 |
O(n*n) |
O(n*n) |
稳定 |
O(1) |
大部分已排序时较好 |
4 |
归并 |
O( n*log(n) ) |
O( n*log(n) ) |
稳定 |
O(1) |
n大时较好 |
5 |
希尔 |
O( n*log(n) ) |
O(n)~O(n*n) |
不稳定 |
O(1) |
看分组情况 |
6 |
快速 |
O( n*log(n) ) |
O(n*n) |
不稳定 |
O(nlogn) |
n大时较好 |
7 |
堆排序 |
O( n*log(n) ) |
O( n*log(n) ) |
不稳定 |
O(1) |
n大时较好 |
8 |
计数 |
未考证 |
未考证 |
|
|
|
9 |
基数 |
O(logRB) |
O(logRB) |
稳定 |
O(n) |
根据数据情况 |
10 |
桶排序 |
未考证 |
未考证 |
|
|
|
按排序时的搜寻特点又可以分为:
编号 |
排序种类 |
|
1 |
交换排序 |
冒泡排序 |
快速排序 |
||
2 |
插入排序 |
直接插入排序 |
二分插入排序 |
||
希尔排序 |
||
3 |
选择排序 |
直接选择排序 |
堆排序 |
||
4 |
分配排序 |
箱排序 |
基数排序 |
||
5 |
归并排序 |
归并排序 |
下面就按这5大类简要的说明一下: