选择排序

    1. function createArr(num) {
    2.   let arr = new Array(num);
    3.   for (let i = 0; i < num; i++) {
    4.     arr[i] = Math.ceil(Math.random() * 10000);
    5.   }
    6.   return arr;
    7. }
    9. function selectSort(arr) {
    10.   console.time();
    11.   let min = 0; //存放最小值
    12.   let minIndex = 0; //寻找最小值的下标
    13.   for (let i = 0; i < arr.length - 1; i++) {
    14.     min = arr[i];
    15.     minIndex = i;
    16.     for (let j = i + 1; j < arr.length; j++) {
    17.       if (min > arr[j]) {
    18.         min = arr[j];
    19.         minIndex = j;
    20.       }
    21.     }
    22.     if (i !== minIndex) {
    23.       //若有比第i个数小的数则交换
    24.       arr[minIndex] = arr[i];
    25.       arr[i] = min;
    26.     }
    27.   }
    28.   console.timeEnd();
    29. }
    31. let targetArr = createArr(80000);
    32. selectSort(targetArr);

    归并排序

    1. function createArr(num) {
    2.     let arr = new Array(num)
    3.     for (let i = 0; i < num; i++) {
    4.         arr[i] = Math.ceil(Math.random() * 10000);
    5.     }
    6.     return arr
    7. }
    9. function mergeSort(arr) {
    10.     console.time()
    11.     _mergeSort(0, arr.length - 1)
    12.     function _mergeSort(left, right) {
    13.         if (left < right) { //假如当前数组长度大于1，有分解空间
    14.             let mid = Math.floor((left + right) / 2)
    15.             _mergeSort(left, mid)
    16.             _mergeSort(mid + 1, right)
    17.             // 这个地方代表left到mid的顺序已经排好   mid+1到right的顺序排好
    18.             let tempArr = new Array(right - left + 1) 
    19.             let i = left
    20.             let j = mid + 1
    21.             let t = 0
    22.             while (i <= mid && j <= right) { //当其中一个有序段已经复制完毕，跳出循环，剩下的数据均为比该序列的数大
    23.                 if (arr[i] <= arr[j]) {
    24.                     tempArr[t] = arr[i]
    25.                     i++
    26.                 } else {
    27.                     tempArr[t] = arr[j]
    28.                     j++
    29.                 }
    30.                 t++
    31.             }
    32.             while (i <= mid) { //左序列剩余数加到数组
    33.                 tempArr[t] = arr[i]
    34.                 t++
    35.                 i++
    36.             }
    37.             while (j <= right) { //右边序列剩余数加到数组
    38.                 tempArr[t] = arr[j]
    39.                 t++
    40.                 j++
    41.             }
    42.             let tempLeft = left //把新数组的数据复制到原数组上
    43.             while (tempLeft <= right) {
    44.                 arr[tempLeft] = tempArr[tempLeft - left]
    45.                 tempLeft++
    46.             }
    48.         }
    49.     }
    50.     console.timeEnd()
    51. }
    53. let arr = createArr(80000)
    54. mergeSort(arr)

    基数排序

    1. function createArr(num) {
    2.     let arr = new Array(num)
    3.     for (let i = 0; i < num; i++) {
    4.         arr[i] = Math.ceil(Math.random() * 10000);
    5.     }
    6.     return arr
    7. }
    9. function radixSort(arr, size) { //size代表数字的最大位数
    10.     console.time()
    11.     let bucket = new Array(10)  //创建十个桶，代表数位0到9
    12.     let bucketCount = new Array(10) //记录每个桶里面有多少数据
    13.     for (let i = 0; i < 10; i++) {
    14.         bucket[i] = new Array(arr.length)
    15.         bucketCount[i] = 0
    16.     }
    18.     for (let i = 0; i < size; i++) {
    19.         let divisor = Math.pow(10, i )
    20.         let base = Math.pow(10, i+1 )  //用这个基取模，出来除以divisor，得出的值的整数部分就是第i+1位的数
    21.         for (let j = 0; j < arr.length; j++) { //根据i+1位数放进桶内
    22.             let index=Math.floor(arr[j] % base/divisor)
    23.             bucket[index][bucketCount[index]] = arr[j]  //假设第i+1位数是1，代表第1个桶添加一个数进去，同时这个桶计数加1
    24.             bucketCount[index]++
    25.         }
    26.         let count=0
    27.         for (let j in bucketCount) { //把桶里的数复制到原数组
    28.            for (let index=0;index<bucketCount[j];index++){
    29.                arr[count]=bucket[j][index]
    30.                count++
    31.            }
    32.             bucketCount[j]=0  //归零，桶里的数已经复制到数组里面，桶内的逻辑空间为0
    33.         }
    34.     }
    35.     console.timeEnd()
    36. }
    37. let arr=createArr(80000)
    38. radixSort(arr,4)