如果你的书架上有10000本书，有一天你想把它们整理一次，你大约需要多长时间呢？
这个问题等价于给10000个大小不同的数排序，问需要多少步骤。
排序有很多方法，比如冒泡法：
  • 首先把所有的数字排成一排；
  • 先让前两个数比较，如果小的在前就不动；
  • 如果大的在前，就把这两个数调换一下位置；
  • 然后比较第二、第三个数，依次类推。
  • 一轮之后，你就能把最大的数放在最后了。
  • 只要连续冒泡9999轮，就能排好一万个数。
但是，在最不利的情况下，排好10000本书，你需要进行大约5000万次比较，1秒钟比较一次，大约需要一年半的时间。冒泡法不是一个特别快速的方法。
好的算法能大大节约你的时间，比如你可以使用归并算法。
  • 首先把10000个数随机分成5000组，每组2个数。
  • 把每一组的2个数按大小排好序。
  • 再把相邻的两组融合，每组4个数排好序。
  • 依次类推，直到融合为1组，排好10000个数。
使用这种方法，排好10000本书，你大约需要比较13万次，只要一天半的时间。
其实，你也可以所有的书往天上一扔，掉下来看是不是排好序了，如果没有就重新扔。使用这种情况，在最优的情况下，一秒就能排好。但一般情况下，都会耗尽一生。
好的算法不光要快速，更要稳定。
继续阅读
阅读原文