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