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

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

选择排序：

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function selectionSort(arr) {

 　　var len = arr.length;

 　　var minIndex, temp;

 　　console.time('选择排序耗时');

 　　for (var i = 0; i < len - 1; i++) {

 　　　　minIndex = i;

 　　　　for (var j = i + 1; j < len; j++) {

 　　　　　　if (arr[j] < arr[minIndex]) { //寻找最小的数

 　　　　　　　　minIndex = j; //将最小数的索引保存

 　　　　　　}

 　　　　}

 　　　　temp = arr[i];

 　　　　arr[i] = arr[minIndex];

 　　　　arr[minIndex] = temp;

 　　}

 　　console.timeEnd('选择排序耗时');

 　　return arr;

 }

 console.log(selectionSort(array));  //使用选择排序的方法排序十次平均耗时：13204.966796875ms

希尔排序：

 //Js中的希尔排序

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function shellSort(arr) {

 　　var len = arr.length,

 　　temp,

 　　gap = 1;

 　　console.time('希尔排序耗时:');

 　　while(gap < len/5) { //动态定义间隔序列

 　　　　gap =gap*5+1;

 　　}

 　　for (gap; gap > 0; gap = Math.floor(gap/5)) {

 　　　　for (var i = gap; i < len; i++) {

 　　　　　　temp = arr[i];

 　　　　　　for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {

 　　　　　　　　arr[j+gap] = arr[j];

 　　　　　　}

 　　　　　　arr[j+gap] = temp;

 　　　　}

 　　}

 　　console.timeEnd('希尔排序耗时:');

 　　return arr;

 }

 console.log(shellSort(array));   //希尔排序十次平均耗时：25.843994140625ms

桶排序：

 //Js中的桶排序

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function bucketSort(array, num) {

 　　if (array.length <= 1) {

 　　　　return array;

 　　}

 　　var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;

 　　var index = Math.floor(len / num) ;

 　　while(index<2){

 　　　　num--;

 　　　　index = Math.floor(len / num) ;

 　　}

 　　console.time('桶排序耗时');

 　　for (var i = 1; i < len; i++) {

 　　　　min = min <= array[i] ? min : array[i];

 　　　　max = max >= array[i] ? max : array[i];

 　　}

 　　space = (max - min + 1) / num;  //步长

 　　for (var j = 0; j < len; j++) {

 　　　　var index = Math.floor((array[j] - min) / space);

 　　　　if (buckets[index]) { // 非空桶，插入排序

 　　　　　　var k = buckets[index].length - 1;

 　　　　　　while (k >= 0 && buckets[index][k] > array[j]) {

 　　　　　　　　buckets[index][k + 1] = buckets[index][k];

 　　　　　　　　k--;

 　　　　　　}

 　　　　　　buckets[index][k + 1] = array[j];

 　　　　} else { //空桶，初始化

 　　　　　　buckets[index] = [];

 　　　　　　buckets[index].push(array[j]);

 　　　　}

 　　}

 　　while (n < num) {

 　　　　result = result.concat(buckets[n]);

 　　　　n++;

 　　}

 　　console.timeEnd('桶排序耗时');

 　　return result;

 }

 console.log(bucketSort(array,1000));    // 桶排序十次平均耗时  ： 122.424072265625ms

快速排序：

 //Js中的快速排序

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 var quickSort = function(arr) {

 　　//console.time('2.快速排序耗时');

 　　if (arr.length <= 1) { return arr; }

 　　var pivotIndex = Math.floor(arr.length / 2);

 　　var pivot = arr.splice(pivotIndex, 1)[0];

 　　var left = [];

 　　var right = [];

 　　for (var i = 0; i < arr.length; i++){

 　　　　if (arr[i] < pivot) {

 　　　　　　left.push(arr[i]);

 　　　　} else {

 　　　　　　right.push(arr[i]);

 　　　　}

 　　}

 　　//console.timeEnd('2.快速排序耗时');

 　　return quickSort(left).concat([pivot], quickSort(right));

 };

 var abc = function(){

       console.time('2.快速排序耗时');

       var efg = quickSort(array);

       console.timeEnd('2.快速排序耗时');

       return efg;

 }

 abc();        //快速排序十次平均耗时：98.901123046875ms

计数排序：

 //Js中的计数排序

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function countingSort(array) {

 　　var len = array.length,

 　　B = [],

 　　C = [],

 　　min = max = array[0];

 　　console.time('计数排序耗时');

 　　for (var i = 0; i < len; i++) {

 　　　　min = min <= array[i] ? min : array[i];

 　　　　max = max >= array[i] ? max : array[i];

 　　　　C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;

 　　}

 　　// 计算排序后的元素下标

 　　for (var j = min; j < max; j++) {

 　　　　C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);　

 　　}

 　　for (var k = len - 1; k >= 0; k--) {

 　　　　B[C[array[k]] - 1] = array[k];

 　　　　C[array[k]]--;

 　　}

 　　console.timeEnd('计数排序耗时');

 　　return B;

 }

 console.log(countingSort(array));          // 计数排序十次平均耗时 ：41.35205078125ms

基数排序：

 //Js中的基数排序

 /*其实基数排序和桶排序挺类似的，都是找一个容器把属于同一类的元素装起来，然后进行排序。

 可以把基数排序类比成已知该序列的最高位，然后以除去相对来说的最低位（可能是个位，可能是十位）剩余的位数为桶数，

 这样一来步长就是10或者100了。但是基数排序相对桶排序又有多了一个亮点，那就是基数排序是先排最低位（个位），

 把最低位一致的放在一个桶里，然后依次取出，再进一位（十位），把十位相同的再放到一个桶里，然后再取出，

 这样经过两次重排序就能得到百位以内的排序序列了，百位，千位也是如此。*/

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function radixSort(arr, maxDigit) {

 　　var mod = 10;

 　　var dev = 1;

 　　var counter = [];

 　　console.time('基数排序耗时');

 　　for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

 　　　　for(var j = 0; j < arr.length; j++) {

 　　　　　　var bucket = parseInt((arr[j] % mod) / dev);

 　　　　　　if(counter[bucket]== null) {

 　　　　　　　　counter[bucket] = [];

 　　　　　　}

 　　　　counter[bucket].push(arr[j]);

 　　　　}

 　　　　var pos = 0;

 　　　　for(var j = 0; j < counter.length; j++) {

 　　　　　　var value = null;

 　　　　　　if(counter[j]!=null) {

 　　　　　　　　while ((value = counter[j].shift()) != null) {

 　　　　　　　　　　arr[pos++] = value;

 　　　　　　　　}

 　　　　　　}

 　　　　}

 　　}

 　　console.timeEnd('基数排序耗时');

 　　return arr;

 }

 //console.log(radixSort(array,1));         //基数排序十次平均耗时：  32.949951171875ms

 console.log(radixSort(array,2));            //基数排序十次平均耗时:    66.570068359375ms

 //但是基数排序也有个弊端，就是必须知道最高位有多少位。

 /*基数排序 vs 计数排序 vs 桶排序

 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

 基数排序：根据键值的每位数字来分配桶

 计数排序：每个桶只存储单一键值

 桶排序：每个桶存储一定范围的数值  */

归并排序：

 //Js中的归并排序

 /*归并排序其实可以类比二分法，二分法其实就是二等分的意思，

 简而言之就是不断和新序列的中间值进行比较。归并排序似乎有异曲同工之妙，

 什么意思呢，就是将一个原始序对等分为两部分，然后不断地对等分新的序列，

 直至序列的长度为1或者2，那么想，如果一个序列为1，那就没有比较的意义了，

 它本身就是之最，如果是两个呢，那直接比较不就完了，把比较之后的值推送到一个新的数组。

 就这样不断地细分，不断的产生子序列，然后把穿产生的新序列作为新的父序列，然后同等级的父序列再比较产生新的祖序列，依次类推。*/

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function mergeSort(arr) { //采用自上而下的递归方法

 　　var len = arr.length;

 　　if(len < 2) {

 　　　　return arr;

 　　}

 　　var middle = Math.floor(len / 2),

 　　left = arr.slice(0, middle),

 　　right = arr.slice(middle);

 　　return merge(mergeSort(left), mergeSort(right));

 }

 function merge(left, right){

 　　var result = [];

 　　

 　　while (left.length && right.length) {

 　　　　if (left[0] <= right[0]) {

 　　　　　　result.push(left.shift());

 　　　　} else {

 　　　　　　result.push(right.shift());

 　　　　}

 　　}

 　　while (left.length){

 　　　　result.push(left.shift());

 　　}

 　　while (right.length){

 　　　　result.push(right.shift());

 　　}

 　　

 　　return result;

 }

 var abc = function(){

       console.time('归并排序耗时');

       var efg = mergeSort(array);

       console.timeEnd('归并排序耗时');

 }

 abc();       //归并排序十次平均耗时：194.84814453125ms

堆排序：

 //Js中的堆排序

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function heapSort(array) {

 　　console.time('堆排序耗时');

 　　//建堆

 　　var heapSize = array.length, temp;

 　　for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {　　

 　　　　heapify(array, i, heapSize);

 　　}

 　　//堆排序

 　　for (var j = heapSize - 1; j >= 1; j--) {

 　　　　temp = array[0];

 　　　　array[0] = array[j];

 　　　　array[j] = temp;

 　　　　heapify(array, 0, --heapSize);

 　　}

 　　console.timeEnd('堆排序耗时');

 　　return array;

 }

 function heapify(arr, x, len) {

 　　var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;

 　　if (l < len && arr[l] > arr[largest]) {

 　　　　largest = l;

 　　}

 　　if (r < len && arr[r] > arr[largest]) {

 　　　　largest = r;

 　　}

 　　if (largest != x) {

 　　　　temp = arr[x];

 　　　　arr[x] = arr[largest];

 　　　　arr[largest] = temp;

 　　　　heapify(arr, largest, len);

 　　}

 }

 console.log(heapSort(array));           //堆排序十次平均耗时：50.8271484375ms

插入排序：

 //Js中的插入排序方法：

 /*插入排序的原理其实很好理解，可以类比选择排序。选择排序时在两个空间进行，

 等于说每次从旧的空间选出最值放到新的空间，而插入排序则是在同一空间进行。

 可以这么理解，在一个数组中我们不知道哪个是最小值，那么就假定第一个就是最小值，

 然后取第二个值与第一个值比较产排序后的序列，然后再取第三个值与排序后的序列进行比较插入到对应的位置，依次类推。*/

 var array = [];

 for(var i=0;i<100000;i++){

      var x = Math.random()*100000;

      var y = Math.floor(x);

      array.push(y);

 }

 function insertionSort(array) {

 　　console.time('插入排序耗时：');

 　　for (var i = 1; i < array.length; i++) {

 　　　　var key = array[i];

 　　　　var j = i - 1;

 　　　　while ( array[j] > key) {

 　　　　　　array[j + 1] = array[j];

 　　　　　    j--;

 　　　　}

 　　　　array[j + 1] = key;

 　　}

 　　console.timeEnd('插入排序耗时：');

 　　return array;

 }

 console.log(insertionSort(array));  //插入排序十次平均耗时：: 33019.146240234375ms

 //插入排序的升级（一）：二分法插入排序

 function binaryInsertionSort(array) {

 　　console.time('二分插入排序耗时：');

 　　for (var i = 1; i < array.length; i++) {

 　　　　var key = array[i], left = 0, right = i - 1;

 　　　　while (left <= right) {

 　　　　　　var middle = parseInt((left + right) / 2);

 　　　　　　if (key < array[middle]) {

 　　　　　　　　right = middle - 1;

 　　　　　　} else {

 　　　　　　　　left = middle + 1;

 　　　　　　}

 　　　　}

 　　　　for (var j = i - 1; j >= left; j--) {

 　　　　　　array[j + 1] = array[j];

 　　　　}

 　　　　array[left] = key;

 　　}

 　　console.timeEnd('二分插入排序耗时：');

 　　return array;

 }

 console.log(binaryInsertionSort(array));           //二分插入排序十次平均耗时:   4326.103759765625ms

巴特西

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

最新文章

热门文章