排序算法总结

声明
本文为Gleasy原创文章,转载请指明引自Gleasy团队博客

一。常用排序算法一览表
排序方法    平均情况     最好情况  最坏情况  辅助空间     稳定性
冒泡排序    O(n2)       O(n)                     O(n2)    O(1)            稳定
简单选择排序  O(n2)       O(n2)         O(n2)     O(1)    稳定
直接插入排序  O(n2)     O(n)           O(n2)      O(1)           稳定
希尔排序    O(nlogn)-O(n2)  O(n1.3)               O(n2)       O(1)    不稳定
堆排序     O(nlogn)      O(nlogn)            O(nlogn)   O(1)     不稳定
归并排序    O(nlogn)     O(nlogn)            O(nlogn)    O(n)     稳定
快速排序    O(nlogn)     O(nlogn)             O(n2)              O(logn)~O(n) 不稳定

二。性能实测
测试方法:随机生成1-100000内的数字,然后放到一个数组里接受排序。
硬件环境:I7 4核8线程,16G内存

测试结果如下:
算法\数量  100  1000 1万         10万 100万 1000万
冒泡排序   0.51   6.8     670         X        X         X
选择排序   0.47   3.31    286.5    X         X         X
插入排序   0.49   2.84    227.95  X         X         X
希尔排序   0.58   0.79    4.39      65.5   1414   18899
堆排序      1.48    1.82     6.3        70.5    1311   15382
归并排序  0.77    1.07     4.5        48.5    682   8064
快速排序  0.8     0.9        2.59      24       345   4562
HPC排序  56       55        56          58        79    734

说明: 时间的单位是MS(1s=1000MS)。HPC排序指并行排序(使用多线程排序)
从上表得出以下结论:
当被排序数据处于100以下时,简单排序用时最短;
当数据量超过1万时,简单排序开始不能胜任,时间呈几何增长;
当数据量超过10万时,简单排序已经失效,跑不出结果;
快速排序表现最为抢眼,是高级排序中用时最短的算法;

三。HPC排序算法介绍
1. 将待排序数据平均分为X个队列(X为CPU的核数)-(Map)
2. 开启X个线程,同时使用高级(快速/堆/归并)排序算法分别对这X个队列进行排序
3. 排序完成的队列进行两两合并,X->X/2->x/4—->1,最终得到1个有序队列 –(Reduce)
4. 排序完成

四。总结
对于大多数情况(不考虑内存占用,假设待排序的数据排列情况随机),在数据量非常小(1000以下时),选择插入排序即可;在数据量位于10万级别以下时,选择快速排序比较稳妥;当数据量超过10万,达到100万以上,HPC排序是不二选择;
对于懒人来说,保险起见,直接选择快速排序也未尝不可,至少在100万以下的数据,还是1S以内可以搞定的。超过1000万,就要HPC排序了(对稳定性有要求可以使用归并排序结合HPC)。

此条目发表在 Java技术, 分布式技术, 数据库技术 分类目录。将固定链接加入收藏夹。

发表评论