你的位置:首页 > Java教程

[Java教程]几种经典排序算法的JS实现


一.冒泡排序

 1 function BubbleSort(array) { 2   var length = array.length; 3   for (var i = length - 1; i > 0; i--) { //用于缩小范围 4     for (var j = 0; j < i; j++) { //在范围内进行冒泡,在此范围内最大的一个将冒到最后面 5       if (array[j] > array[j+1]) {  6         var temp = array[j]; 7         array[j] = array[j+1]; 8         array[j+1] = temp; 9       }10     }11     console.log(array);12     console.log("-----------------------------");13   }14   return array;15 }16 17 18 var arr = [10,9,8,7,7,6,5,11,3];19 var result = BubbleSort(arr);20 console.log(result); 21 /*22 [ 9, 8, 7, 7, 6, 5, 10, 3, 11 ]23 -----------------------------24 [ 8, 7, 7, 6, 5, 9, 3, 10, 11 ]25 -----------------------------26 [ 7, 7, 6, 5, 8, 3, 9, 10, 11 ]27 -----------------------------28 [ 7, 6, 5, 7, 3, 8, 9, 10, 11 ]29 -----------------------------30 [ 6, 5, 7, 3, 7, 8, 9, 10, 11 ]31 -----------------------------32 [ 5, 6, 3, 7, 7, 8, 9, 10, 11 ]33 -----------------------------34 [ 5, 3, 6, 7, 7, 8, 9, 10, 11 ]35 -----------------------------36 [ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]37 -----------------------------38 [ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]39 */

 

二.选择排序

 1 function SelectionSort(array) { 2   var length = array.length; 3   for (var i = 0; i < length; i++) { //缩小选择的范围 4     var min = array[i]; //假定范围内第一个为最小值 5     var index = i; //记录最小值的下标 6     for (var j = i + 1; j < length; j++) { //在范围内选取最小值 7       if (array[j] < min) { 8         min = array[j]; 9         index = j;10       }11     }12     if (index != i) { //把范围内最小值交换到范围内第一个13       var temp = array[i];14       array[i] = array[index];15       array[index] = temp;16     }17     console.log(array);18     console.log("---------------------");19   }20   return array;21 }22 23 var arr = [ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ];24 var result = SelectionSort(arr);25 console.log(result);26 /*27 [ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ]28 ---------------------29 [ 1, 2, 100, 90, 65, 5, 4, 10, 10, 4 ]30 ---------------------31 [ 1, 2, 4, 90, 65, 5, 100, 10, 10, 4 ]32 ---------------------33 [ 1, 2, 4, 4, 65, 5, 100, 10, 10, 90 ]34 ---------------------35 [ 1, 2, 4, 4, 5, 65, 100, 10, 10, 90 ]36 ---------------------37 [ 1, 2, 4, 4, 5, 10, 100, 65, 10, 90 ]38 ---------------------39 [ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]40 ---------------------41 [ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]42 ---------------------43 [ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]44 ---------------------45 [ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]46 ---------------------47 [ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]48 */

 

三.插入排序

 1 function InsertionSort(array) { 2   var length = array.length; 3   for (var i = 0; i < length - 1; i++) { 4     //i代表已经排序好的序列最后一项下标 5     var insert = array[i+1]; 6     var index = i + 1;//记录要被插入的下标 7     for (var j = i; j >= 0; j--) { 8       if (insert < array[j]) { 9         //要插入的项比它小,往后移动10         array[j+1] = array[j];11         index = j;12       }13     }14     array[index] = insert;15     console.log(array);16     console.log("-----------------------");17   }18   return array;19 }20 21 var arr = [100,90,80,62,80,8,1,2,39];22 var result = InsertionSort(arr);23 console.log(result);24 /*25 [ 90, 100, 80, 62, 80, 8, 1, 2, 39 ]26 -----------------------27 [ 80, 90, 100, 62, 80, 8, 1, 2, 39 ]28 -----------------------29 [ 62, 80, 90, 100, 80, 8, 1, 2, 39 ]30 -----------------------31 [ 62, 80, 80, 90, 100, 8, 1, 2, 39 ]32 -----------------------33 [ 8, 62, 80, 80, 90, 100, 1, 2, 39 ]34 -----------------------35 [ 1, 8, 62, 80, 80, 90, 100, 2, 39 ]36 -----------------------37 [ 1, 2, 8, 62, 80, 80, 90, 100, 39 ]38 -----------------------39 [ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]40 -----------------------41 [ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]42 */

 

四.希尔排序

 1 function ShellSort(array) { 2   var length = array.length; 3   var gap = Math.round(length / 2); 4   while (gap > 0) { 5     for (var i = gap; i < length; i++) { 6       var insert = array[i]; 7       var index = i; 8       for (var j = i; j >= 0; j-=gap) { 9         if (insert < array[j]) {10           array[j+gap] = array[j];11           index = j;12         }13       }14       array[index] = insert;15     }16     console.log(array);17     console.log("-----------------------");18     gap = Math.round(gap/2 - 0.1);19   }20   return array;21 }22 23 var arr = [ 13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10 ];24 var result = ShellSort(arr);25 console.log(result); 26 /*27 [ 13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94 ]28 -----------------------29 [ 13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94 ]30 -----------------------31 [ 13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94 ]32 -----------------------33 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]34 -----------------------35 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]36 */

 

五.归并排序

 1 function MergeSort(array) { 2   var length = array.length; 3   if (length <= 1) { 4     return array; 5   } else { 6     var num = Math.ceil(length/2); 7     var left = MergeSort(array.slice(0, num)); 8     var right = MergeSort(array.slice(num, length)); 9     return merge(left, right); 10   } 11 } 12  13 function merge(left, right) { 14   console.log(left); 15   console.log(right); 16   var a = new Array(); 17   while (left.length > 0 && right.length > 0) { 18     if (left[0] <= right[0]) { 19       var temp = left.shift(); 20       a.push(temp); 21     } else { 22       var temp = right.shift(); 23       a.push(temp); 24     } 25   } 26   if (left.length > 0) { 27     a = a.concat(left); 28   } 29   if (right.length > 0) { 30     a = a.concat(right); 31   } 32   console.log(a); 33   console.log("-----------------------------"); 34   return a; 35 } 36  37 var arr = [ 13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10 ]; 38 var result = MergeSort(arr); 39 console.log(result); 40 /* 41 [ 13 ] 42 [ 14 ] 43 [ 13, 14 ] 44 ----------------------------- 45 [ 94 ] 46 [ 33 ] 47 [ 33, 94 ] 48 ----------------------------- 49 [ 13, 14 ] 50 [ 33, 94 ] 51 [ 13, 14, 33, 94 ] 52 ----------------------------- 53 [ 82 ] 54 [ 25 ] 55 [ 25, 82 ] 56 ----------------------------- 57 [ 59 ] 58 [ 94 ] 59 [ 59, 94 ] 60 ----------------------------- 61 [ 25, 82 ] 62 [ 59, 94 ] 63 [ 25, 59, 82, 94 ] 64 ----------------------------- 65 [ 13, 14, 33, 94 ] 66 [ 25, 59, 82, 94 ] 67 [ 13, 14, 25, 33, 59, 82, 94, 94 ] 68 ----------------------------- 69 [ 65 ] 70 [ 23 ] 71 [ 23, 65 ] 72 ----------------------------- 73 [ 45 ] 74 [ 27 ] 75 [ 27, 45 ] 76 ----------------------------- 77 [ 23, 65 ] 78 [ 27, 45 ] 79 [ 23, 27, 45, 65 ] 80 ----------------------------- 81 [ 73 ] 82 [ 25 ] 83 [ 25, 73 ] 84 ----------------------------- 85 [ 39 ] 86 [ 10 ] 87 [ 10, 39 ] 88 ----------------------------- 89 [ 25, 73 ] 90 [ 10, 39 ] 91 [ 10, 25, 39, 73 ] 92 ----------------------------- 93 [ 23, 27, 45, 65 ] 94 [ 10, 25, 39, 73 ] 95 [ 10, 23, 25, 27, 39, 45, 65, 73 ] 96 ----------------------------- 97 [ 13, 14, 25, 33, 59, 82, 94, 94 ] 98 [ 10, 23, 25, 27, 39, 45, 65, 73 ] 99 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]100 -----------------------------101 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]102 */

 

六.快速排序

 1 function QuickSort(array) { 2   var length = array.length; 3   if (length <= 1) { 4     return array; 5   } else { 6     var smaller = []; 7     var bigger = []; 8     var base = [array[0]]; 9     for (var i = 1; i < length; i++) {10       if (array[i] <= base[0]) {11         smaller.push(array[i]);12       } else {13         bigger.push(array[i]);14       }15     }16     console.log(smaller.concat(base.concat(bigger)));17     console.log("-----------------------");18     return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));19   }20 }21 22 23 var arr = [ 8, 10, 100, 90, 65, 5, 4, 10, 2, 4 ];24 var result = QuickSort(arr);25 console.log(result);26 /*27 [ 5, 4, 2, 4, 8, 10, 100, 90, 65, 10 ]28 -----------------------29 [ 4, 2, 4, 5 ]30 -----------------------31 [ 2, 4, 4 ]32 -----------------------33 [ 2, 4 ]34 -----------------------35 [ 10, 10, 100, 90, 65 ]36 -----------------------37 [ 90, 65, 100 ]38 -----------------------39 [ 65, 90 ]40 -----------------------41 [ 2, 4, 4, 5, 8, 10, 10, 65, 90, 100 ]42 */