排序算法 Sleep Sort
排序算法好像是程序员学习编程最多的算法,也可能是算法研究者们最喜欢研究的算法了。排序有很多很多的算法,比如,冒泡,插入,选择,堆,快速,归并等等(你可以看看本站以前的那些文章:可视化的排序,排序算法比较,显示排序过程的python)这里向大家介绍一个“巨NB”的排序算法――Sleep Sort。
闲言少说,请看下面的代码(用Shell脚本写的)
#!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait
用法如下:
./sleepsort.bash 5 3 6 3 6 3 1 4 7
相信你可以会去试一下这个脚本,也相你你试完后你一定会说――“我擦,真TMD排序了!”,我还是不要解释这段代码了,过多的解释会不如代码那么直接,而且解释会影响你对这个排序算法的NB性。只想说――这是正二八经的多线程、多进程排序啊。我们的Bogo排序也黯然失色啊。
下面我们需要对这个算法做一些分析――
1)让我们来分析一个这这个程序的算法复杂度,太简单了,不就是O(最大数的秒数),呵呵。所以,如果出现这样的数列将是恶梦的――2 1 4 3 2 1 99999999
2)这个排序好是好,但对于负数或浮点数就有bug了。负数的解决方案是,我们可以这样来:x/2+MaxInt/2(时间可能相当长,不过依然工作)。对于浮点数,看看下面的代码.
#!/bin/bash function f() { sleep $(echo "($2 - 1) + $1 / 10 ^ $2" | bc -l) echo "$1" } while [ -n "$1" ] do f "$1" $(echo -n "$1" | wc -c) & shift done wait
3)我们来看看各种语言版本的实现吧。
Java
public class SleepSort { public static void main(String[] args) { int[] ints = {1,4,7,3,8,9,2,6,5}; SortThread[] sortThreads = new SortThread[ints.length]; for (int i = 0; i < sortThreads.length; i++) { sortThreads[i] = new SortThread(ints[i]); } for (int i = 0; i < sortThreads.length; i++) { sortThreads[i].start(); } } } class SortThread extends Thread{ int ms = 0; public SortThread(int ms){ this.ms = ms; } public void run(){ try { sleep(ms*10+10); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } System.out.println(ms); } }
Javascript
function sleepsort() { for (var i = 0, il = arguments.length; i < il; i++) { (function(args, index) { setTimeout(function() { document.body.innerHTML += args[index] + \', \'; }, args[index]); }(arguments, i)); } };
Brainfuck (关于这门语言,请参看这篇文章)
,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+,>,>++++++++[<------<------>>-]
<<[ ----------[++++++++++>----------]++++++++++
>[>+>+<<-]>>[<<+>>-]<<<-] >>>++++++[<++++++++>-]<.>.>>-]<<<-]
,----------[----------------------.,----------]
,---<<<+>>>-------[----------------------.,----------]
>> ----------[++++++++++>----------]++++++++++
>++++++[<++++++++>-]< ----------[++++++++++>----------]++++++++++
.>. ----------[++++++++++>----------]++++++++++
>++>+<<-]>>[<<+>>-]<<<-] >>[>[>+>+<<-]>>[<<----------[++++++++++>----------]++++++++++
>++,>,>++++++++[<------<------>>-]
<<
(全文完)
建议继续学习:
- 如何使用1M的内存排序100万个8位数 (阅读:10901)
- 快速排序(Quicksort)的Javascript实现 (阅读:10089)
- 腾讯-1亿个数据取前1万大的整数-题解答 (阅读:9042)
- 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序) (阅读:6188)
- 深入浅出交换类排序算法(冒泡排序,快速排序) (阅读:5986)
- Java程序员必知的8大排序算法 (阅读:4458)
- Mysql中的排序优化 (阅读:4359)
- Vim(gVim)对排序的妙用 (阅读:4221)
- 快速排序详细分析 (阅读:3955)
- 深入浅出选择类排序算法(简单选择排序,堆排序) (阅读:3753)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:陈皓 来源: 酷壳 - CoolShell.cn
- 标签: 排序
- 发布时间:2011-06-23 13:32:01
- [55] Oracle MTS模式下 进程地址与会话信
- [55] IOS安全–浅谈关于IOS加固的几种方法
- [54] 如何拿下简短的域名
- [53] android 开发入门
- [52] 图书馆的世界纪录
- [52] Go Reflect 性能
- [49] 读书笔记-壹百度:百度十年千倍的29条法则
- [47] 【社会化设计】自我(self)部分――欢迎区
- [38] 程序员技术练级攻略
- [32] 视觉调整-设计师 vs. 逻辑