Javascript十大排序算法的实现方法

上一篇中,实现了Javascript中的冒泡排序方法,下面把剩余的九种排序算法实现

选择排序:

 1 var array = [];
 2 
 3 for(var i=0;i<100000;i++){
 4      var x = Math.random()*100000;
 5      var y = Math.floor(x);
 6      array.push(y);
 7 }
 8 
 9 function selectionSort(arr) {
10   var len = arr.length;
11   var minIndex, temp;
12   console.time('选择排序耗时');
13   for (var i = 0; i < len - 1; i++) {
14     minIndex = i;
15     for (var j = i + 1; j < len; j++) {
16       if (arr[j] < arr[minIndex]) { //寻找最小的数
17         minIndex = j; //将最小数的索引保存
18       }
19     }
20     temp = arr[i];
21     arr[i] = arr[minIndex];
22     arr[minIndex] = temp;
23   }
24   console.timeEnd('选择排序耗时');
25   return arr;
26 }
27 
28 console.log(selectionSort(array));  //使用选择排序的方法排序十次平均耗时:13204.966796875ms

希尔排序:

 1 //Js中的希尔排序
 2 
 3 var array = [];
 4 
 5 for(var i=0;i<100000;i++){
 6      var x = Math.random()*100000;
 7      var y = Math.floor(x);
 8      array.push(y);
 9 }
10 
11 
12 function shellSort(arr) {
13   var len = arr.length,
14   temp,
15   gap = 1;
16   console.time('希尔排序耗时:');
17   while(gap < len/5) { //动态定义间隔序列
18     gap =gap*5+1;
19   }
20   for (gap; gap > 0; gap = Math.floor(gap/5)) {
21     for (var i = gap; i < len; i++) {
22       temp = arr[i];
23       for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
24         arr[j+gap] = arr[j];
25       }
26       arr[j+gap] = temp;
27     }
28   }
29   console.timeEnd('希尔排序耗时:');
30   return arr;
31 }
32 
33 console.log(shellSort(array));   //希尔排序十次平均耗时:25.843994140625ms

桶排序:

 1 //Js中的桶排序
 2 
 3 var array = [];
 4 
 5 for(var i=0;i<100000;i++){
 6      var x = Math.random()*100000;
 7      var y = Math.floor(x);
 8      array.push(y);
 9 }
10 
11 function bucketSort(array, num) {
12   if (array.length <= 1) {
13     return array;
14   }
15   var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;
16 
17   var index = Math.floor(len / num) ;
18   while(index<2){
19     num--;
20     index = Math.floor(len / num) ;
21   }
22 
23   console.time('桶排序耗时');
24   for (var i = 1; i < len; i++) {
25     min = min <= array[i] ? min : array[i];
26     max = max >= array[i] ? max : array[i];
27   }
28   space = (max - min + 1) / num;  //步长
29   for (var j = 0; j < len; j++) {
30     var index = Math.floor((array[j] - min) / space);
31     if (buckets[index]) { // 非空桶,插入排序
32       var k = buckets[index].length - 1;
33       while (k >= 0 && buckets[index][k] > array[j]) {
34         buckets[index][k + 1] = buckets[index][k];
35         k--;
36       }
37       buckets[index][k + 1] = array[j];
38     } else { //空桶,初始化
39       buckets[index] = [];
40       buckets[index].push(array[j]);
41     }
42   }
43   while (n < num) {
44     result = result.concat(buckets[n]);
45     n++;
46   }
47   console.timeEnd('桶排序耗时');
48   return result;
49 }
50 
51 console.log(bucketSort(array,1000));    // 桶排序十次平均耗时  : 122.424072265625ms

快速排序:

 1 //Js中的快速排序
 2 
 3 var array = [];
 4 
 5 for(var i=0;i<100000;i++){
 6      var x = Math.random()*100000;
 7      var y = Math.floor(x);
 8      array.push(y);
 9 }
10 
11 var quickSort = function(arr) {
12   //console.time('2.快速排序耗时');
13   if (arr.length <= 1) { return arr; }
14   var pivotIndex = Math.floor(arr.length / 2);
15   var pivot = arr.splice(pivotIndex, 1)[0];
16   var left = [];
17   var right = [];
18   for (var i = 0; i < arr.length; i++){
19     if (arr[i] < pivot) {
20       left.push(arr[i]);
21     } else {
22       right.push(arr[i]);
23     }
24   }
25   //console.timeEnd('2.快速排序耗时');
26   return quickSort(left).concat([pivot], quickSort(right));
27 };
28 
29 var abc = function(){
30       console.time('2.快速排序耗时');
31       var efg = quickSort(array);
32       console.timeEnd('2.快速排序耗时');
33       return efg;
34 }
35 
36 abc();        //快速排序十次平均耗时:98.901123046875ms           

计数排序:

 1 //Js中的计数排序
 2 
 3 var array = [];
 4 
 5 for(var i=0;i<100000;i++){
 6      var x = Math.random()*100000;
 7      var y = Math.floor(x);
 8      array.push(y);
 9 }
10 
11 function countingSort(array) {
12   var len = array.length,
13   B = [],
14   C = [],
15   min = max = array[0];
16   console.time('计数排序耗时');
17   for (var i = 0; i < len; i++) {
18     min = min <= array[i] ? min : array[i];
19     max = max >= array[i] ? max : array[i];
20     C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
21   }
22 
23   // 计算排序后的元素下标
24   for (var j = min; j < max; j++) {
25     C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); 
26   }
27   for (var k = len - 1; k >= 0; k--) {
28     B[C[array[k]] - 1] = array[k];
29     C[array[k]]--;
30   }
31   console.timeEnd('计数排序耗时');
32   return B;
33 }
34 
35 
36 console.log(countingSort(array));          // 计数排序十次平均耗时 :41.35205078125ms

基数排序:

 1 //Js中的基数排序
 2 
 3 /*其实基数排序和桶排序挺类似的,都是找一个容器把属于同一类的元素装起来,然后进行排序。
 4 可以把基数排序类比成已知该序列的最高位,然后以除去相对来说的最低位(可能是个位,可能是十位)剩余的位数为桶数,
 5 这样一来步长就是10或者100了。但是基数排序相对桶排序又有多了一个亮点,那就是基数排序是先排最低位(个位),
 6 把最低位一致的放在一个桶里,然后依次取出,再进一位(十位),把十位相同的再放到一个桶里,然后再取出,
 7 这样经过两次重排序就能得到百位以内的排序序列了,百位,千位也是如此。*/
 8 
 9 var array = [];
10 
11 for(var i=0;i<100000;i++){
12      var x = Math.random()*100000;
13      var y = Math.floor(x);
14      array.push(y);
15 }
16 
17 function radixSort(arr, maxDigit) {
18   var mod = 10;
19   var dev = 1;
20   var counter = [];
21   console.time('基数排序耗时');
22   for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
23     for(var j = 0; j < arr.length; j++) {
24       var bucket = parseInt((arr[j] % mod) / dev);
25       if(counter[bucket]== null) {
26         counter[bucket] = [];
27       }
28     counter[bucket].push(arr[j]);
29     }
30     var pos = 0;
31     for(var j = 0; j < counter.length; j++) {
32       var value = null;
33       if(counter[j]!=null) {
34         while ((value = counter[j].shift()) != null) {
35           arr[pos++] = value;
36         }
37       }
38     }
39   }
40   console.timeEnd('基数排序耗时');
41   return arr;
42 }
43 
44 //console.log(radixSort(array,1));         //基数排序十次平均耗时:  32.949951171875ms
45 
46 
47 console.log(radixSort(array,2));            //基数排序十次平均耗时:    66.570068359375ms
48 
49 
50 //但是基数排序也有个弊端,就是必须知道最高位有多少位。
51 /*基数排序 vs 计数排序 vs 桶排序
52 
53 这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
54 
55 基数排序:根据键值的每位数字来分配桶
56 计数排序:每个桶只存储单一键值
57 桶排序:每个桶存储一定范围的数值  */

归并排序:

 1 //Js中的归并排序
 2 
 3 /*归并排序其实可以类比二分法,二分法其实就是二等分的意思,
 4 简而言之就是不断和新序列的中间值进行比较。归并排序似乎有异曲同工之妙,
 5 什么意思呢,就是将一个原始序对等分为两部分,然后不断地对等分新的序列,
 6 直至序列的长度为1或者2,那么想,如果一个序列为1,那就没有比较的意义了,
 7 它本身就是之最,如果是两个呢,那直接比较不就完了,把比较之后的值推送到一个新的数组。
 8 就这样不断地细分,不断的产生子序列,然后把穿产生的新序列作为新的父序列,然后同等级的父序列再比较产生新的祖序列,依次类推。*/
 9 
10 var array = [];
11 
12 for(var i=0;i<100000;i++){
13      var x = Math.random()*100000;
14      var y = Math.floor(x);
15      array.push(y);
16 }
17 
18 function mergeSort(arr) { //采用自上而下的递归方法
19   var len = arr.length;
20   if(len < 2) {
21     return arr;
22   }
23   var middle = Math.floor(len / 2),
24   left = arr.slice(0, middle),
25   right = arr.slice(middle);
26   return merge(mergeSort(left), mergeSort(right));
27 }
28  
29 function merge(left, right){
30   var result = [];
31   
32   while (left.length && right.length) {
33     if (left[0] <= right[0]) {
34       result.push(left.shift());
35     } else {
36       result.push(right.shift());
37     }
38   }
39  
40   while (left.length){
41     result.push(left.shift());
42   }
43   while (right.length){
44     result.push(right.shift());
45   }
46   
47   return result;
48 }
49 
50 var abc = function(){
51       console.time('归并排序耗时');
52       var efg = mergeSort(array);
53       console.timeEnd('归并排序耗时');
54 }
55 
56 abc();       //归并排序十次平均耗时:194.84814453125ms

堆排序:

 1 //Js中的堆排序
 2 
 3 var array = [];
 4 
 5 for(var i=0;i<100000;i++){
 6      var x = Math.random()*100000;
 7      var y = Math.floor(x);
 8      array.push(y);
 9 }
10 
11 function heapSort(array) {
12   console.time('堆排序耗时');
13   //建堆
14   var heapSize = array.length, temp;
15   for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {  
16     heapify(array, i, heapSize);
17   }
18   //堆排序
19   for (var j = heapSize - 1; j >= 1; j--) {
20     temp = array[0];
21     array[0] = array[j];
22     array[j] = temp;
23     heapify(array, 0, --heapSize);
24   }
25   console.timeEnd('堆排序耗时');
26   return array;
27 }
28 function heapify(arr, x, len) {
29   var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
30   if (l < len && arr[l] > arr[largest]) {
31     largest = l;
32   }
33   if (r < len && arr[r] > arr[largest]) {
34     largest = r;
35   }
36   if (largest != x) {
37     temp = arr[x];
38     arr[x] = arr[largest];
39     arr[largest] = temp;
40     heapify(arr, largest, len);
41   }
42 }
43 
44 console.log(heapSort(array));           //堆排序十次平均耗时:50.8271484375ms

插入排序:

 1 //Js中的插入排序方法:
 2 
 3 /*插入排序的原理其实很好理解,可以类比选择排序。选择排序时在两个空间进行,
 4 等于说每次从旧的空间选出最值放到新的空间,而插入排序则是在同一空间进行。
 5 可以这么理解,在一个数组中我们不知道哪个是最小值,那么就假定第一个就是最小值,
 6 然后取第二个值与第一个值比较产排序后的序列,然后再取第三个值与排序后的序列进行比较插入到对应的位置,依次类推。*/
 7 
 8 var array = [];
 9 
10 for(var i=0;i<100000;i++){
11      var x = Math.random()*100000;
12      var y = Math.floor(x);
13      array.push(y);
14 }
15 
16 function insertionSort(array) {
17   console.time('插入排序耗时:');
18   for (var i = 1; i < array.length; i++) {
19     var key = array[i];
20     var j = i - 1;
21     while ( array[j] > key) {
22       array[j + 1] = array[j];
23          j--;
24     }
25     array[j + 1] = key;
26   }
27   console.timeEnd('插入排序耗时:');
28   return array;
29 }
30 
31 console.log(insertionSort(array));  //插入排序十次平均耗时:: 33019.146240234375ms
32 
33 
34 //插入排序的升级(一):二分法插入排序
35 
36 function binaryInsertionSort(array) {
37   console.time('二分插入排序耗时:');
38   for (var i = 1; i < array.length; i++) {
39     var key = array[i], left = 0, right = i - 1;
40     while (left <= right) {
41       var middle = parseInt((left + right) / 2);
42       if (key < array[middle]) {
43         right = middle - 1;
44       } else {
45         left = middle + 1;
46       }
47     }
48     for (var j = i - 1; j >= left; j--) {
49       array[j + 1] = array[j];
50     }
51     array[left] = key;
52   }
53   console.timeEnd('二分插入排序耗时:');
54   return array;
55 }
56 
57 console.log(binaryInsertionSort(array));           //二分插入排序十次平均耗时:   4326.103759765625ms
原文地址:https://www.cnblogs.com/liquanjiang/p/8747697.html