JS家的排序算法

  当年,想凭借抱Java大腿火一把而不惜把自己名字给改了的Java(原名Live),如今早已光芒万丈。node JS的出现更是让Java可以前后端通吃。虽然Java依然制霸企业级软件开发领域(C/C + +的大神们不要打我。。。),但在Web的江湖,Java可谓风头无两,坐上了头把交椅。

  然而,在传统的计算机算法和数据结构领域,大多数专业教材和书籍的默认语言都是Java或者C/C+ +。这给最近想恶补算法和数据结构知识的我造成了一定困扰,因为我想寻找一本以Java为默认语言的算法书籍。当我了解到O’REILLY家的动物丛书系列里有一本叫做《数据结构与算法Java描述》时,便兴奋的花了两天时间把这本书从头到尾读了一遍。它是一本很好的针对前端开发者们的入门算法书籍,可是,它有一个很大的缺陷,就是里面有很多明显的小错误,明显到就连我这种半路出家的程序猿都能一眼看出来。还有一个问题是,很多重要的算法和数据结构知识并没有在这本书里被提到。这些问题对于作为一个晚期强迫症患者的我来说简直不能忍。于是乎,一言不合我就决定自己找资料总结算法。那么,我就从算法领域里最基础的知识点——排序算法总结起好了。

  我相信以下的代码里一定会有某些bug或错误或语法不规范等问题是我自己无法发现的,所以敬请各位大神能够指出错误,因为只有在不断改错的道路上我才能取得长久的进步。

  作为最简单的排序算法之一,冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。。。冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。

  当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊。。。。)

  当输入的数据是反序时(写一个for循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗。。。)

  在时间复杂度上表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

  插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌,那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。

  插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。对于这种算法,得了懒癌的我就套用教科书上的一句经典的话吧:感兴趣的同学可以在课后自行研究。。。

  希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。在这里,我就使用了这种方法。

  在《数据结构与算法Java描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

  然而,在 Java 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

  说实话,我不太理解这句话。意思是Java编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。

  和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。

  又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

  快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好,可是这是为什么呢,我也不知道。。。好在我的强迫症又犯了,查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

  快速排序的最坏运行情况是O(n²),比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ,且O(n log n)记号中隐含的常数因子很小,比复杂度稳定等于O(n log n)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

  作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

  桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。

相关阅读