JS的各种排序算法实现

一些排序算法

  1. var Sort = {}
  2. Sort.prototype = {
  3. // 利用sort进行排序
  4. systemSort:function(array){
  5. return array.sort(function(a, b){
  6. return a - b;
  7. });
  8. },
  9. // 冒泡排序
  10. bubbleSort:function(array){
  11. var i = 0, len = array.length,
  12. j, d;
  13. for(; i<len; i++){
  14. for(j=0; j<len; j++){
  15. if(array[i] < array[j]){
  16. d = array[j];
  17. array[j] = array[i];
  18. array[i] = d;
  19. }
  20. }
  21. }
  22. return array;
  23. },
  24. // 快速排序
  25. quickSort:function(array){
  26. //var array = [8,4,6,2,7,9,3,5,74,5];
  27. //var array =[0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
  28. var i = 0;
  29. var j = array.length - 1;
  30. var Sort = function(i, j){
  31. // 结束条件
  32. if(i == j ){ return };
  33. var key = array[i];
  34. var tempi = i; // 记录开始位置
  35. var tempj = j; // 记录结束位置
  36. while(j > i){
  37. // j <<-------------- 向前查找
  38. if(array[j] >= key){
  39. j--;
  40. }else{
  41. array[i] = array[j]
  42. //i++ ------------>>向后查找
  43. while(j > ++i){
  44. if(array[i] > key){
  45. array[j] = array[i];
  46. break;
  47. }
  48. }
  49. }
  50. }
  51. // 如果第一个取出的 key 是最小的数
  52. if(tempi == i){
  53. Sort(++i, tempj);
  54. return ;
  55. }
  56. // 最后一个空位留给 key
  57. array[i] = key;
  58. // 递归
  59. Sort(tempi, i);
  60. Sort(j, tempj);
  61. }
  62. Sort(i, j);
  63. return array;
  64. },
  65. // 插入排序
  66. insertSort:function(array){
  67. // var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
  68. var i = 1, j, temp, key, len = array.length;
  69. for(; i < len; i++){
  70. temp = j = i;
  71. key = array[j];
  72. while(--j > -1){
  73. if(array[j] > key){
  74. array[j+1] = array[j];
  75. }else{
  76. break;
  77. }
  78. }
  79. array[j+1] = key;
  80. }
  81. return array;
  82. },
  83. // 希尔排序
  84. //Jun.array.shellSort(Jun.array.df(10000));
  85. shellSort:function(array){
  86. // var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
  87. // var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
  88. // reverse() 在维基上看到这个最优的步长 较小数组
  89. var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]
  90. //针对大数组的步长选择
  91. var i = 0;
  92. var tempArrtempArrLength = tempArr.length;
  93. var len = array.length;
  94. var len2 = parseInt(len/2);
  95. for(;i < tempArrLength; i++){
  96. if(tempArr[i] > len2){
  97. continue;
  98. }
  99. tempSort(tempArr[i]);
  100. }
  101. // 排序一个步长
  102. function tempSort(temp){
  103. //console.log(temp) 使用的步长统计
  104. var i = 0, j = 0, f, tem, key;
  105. var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
  106. for(;i < temp; i++){// 依次循环列
  107. for(j=1;/*j < tempLen && */temp * j + i < len; j++){
  108. //依次循环每列的每行
  109. tem = f = temp * j + i;
  110. key = array[f];
  111. while((tem-=temp) >= 0){
  112. // 依次向上查找
  113. if(array[tem] > key){
  114. array[tem+temp] = array[tem];
  115. }else{
  116. break;
  117. }
  118. }
  119. array[tem + temp ] = key;
  120. }
  121. }
  122. }
  123. return array;
  124. }
  125. }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

51 Nod 1028 大数乘法 V2【Java大数乱搞】

1028 大数乘法 V2 基准时间限制:2 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 给出2个大整数A,B,计算A*B的结果。 Inpu...

2534
来自专栏Python小屋

Python版快速排序算法

快速排序算法是分治法的经典应用,具有非常高的效率。 import random def quickSort(x, start, end): if start...

2905
来自专栏于晓飞的专栏

DualPivotQuickSort 双轴快速排序 源码 笔记

这个算法是Arrays.java中给基本类型的数据排序使用的具体实现。它针对每种基本类型都做了实现,实现的方式有稍微的差异,但是思路都是相同的,所以这里只挑了i...

592
来自专栏IT可乐

Java数据结构和算法(八)——递归

  记得小时候经常讲的一个故事:从前有座山,山上有座庙,庙里有一个老和尚和一个小和尚,一天,老和尚给小和尚讲了一个故事,故事内容是“从前有座山,山上有座庙,庙里...

2267
来自专栏工科狗和生物喵

【计算机本科补全计划】链式存储线性表的一些相关操作

正文之前 不管怎么说,好歹是吧王道的第二章看完了!线性表算法写的我都快吐了,不过成果也是有的,可以写一些稍微复杂的算法了!感动,希望尽早达到老师的要求,然后去实...

2856
来自专栏程序生活

Leetcode-Easy 575. Distribute Candies

728. Self Dividing Numbers 描述: 有偶数个糖,需要分给弟弟和妹妹,要求最终两个人分到的糖数目一样,返回妹妹获得糖的种类数目最大值 ...

3394
来自专栏屈定‘s Blog

算法回顾--如何写递归?

总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

1222
来自专栏苦逼的码农

从0打卡leetcode之day8--反转整数

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

1144
来自专栏用户画像

7.7.3 多路平衡归并与败者树

归并趟数S=[logm R](向下取整)。从而增加归并路数m可以减少归并趟数S,进而减少访问外存的次数(I/O次数)。然而,当增加归并路数m时,内部归并时间将增...

572
来自专栏和蔼的张星的图像处理专栏

156. 合并区间先排序再处理

给出若干闭合区间,合并所有重叠的部分。 样例 给出的区间列表 => 合并后的区间列表:

923

扫码关注云+社区