计数排序

  1. var arr = [4,4,6,5,3,2,8,1,7,5,6,0,10];
  3. countSort(arr);
  5. function countSort(arr) {
  6.   const __list = [];
  7.   let max = arr[0];
  8.     for (let i = 0; i < arr.length; i++) {
  9.     if (max < arr[i]) {
  10.        max = arr[i]
  11.     }
  12.   }
  14.   __list.length = max + 1;
  15.   __list.fill(0);
  17.   for (let i = 0; i < arr.length; i++) {
  18.           __list[arr[i]]++;
  19.   }
  20.     console.log(__list);
  21.     return __list;
  22. }
  24. VM3229:20 (11) [1, 1, 1, 1, 2, 2, 2, 1, 1, 0, 1]

计数排序优化

  1. var arr = [90,99,95,94,95];
  3. countSort(arr);
  5. function countSort(arr) {
  6.   const __list = [];
  7.   let max = arr[0];
  8.   let min = arr[0];
  9.   for (let i = 0; i < arr.length; i++) {
  10.     if (max < arr[i]) {
  11.        max = arr[i];
  12.     }
  13.     if (min > arr[i]) {
  14.       min = arr[i];
  15.     }
  16.   }
  17.   const len = max - min;
  18.   debugger;
  19.   __list.length = len + 1;
  20.   __list.fill(0);
  22.   for (let i = 0; i < arr.length; i++) {
  23.           __list[arr[i] - min]++;
  24.   }
  25.   console.log(__list);
  26.   return __list;
  27. }
  28. /*
  29. 99 - 90 = 9 
  30. [1, 0, 0, 0, 1, 2, 0, 0, 0, 1]
  31. */
  1. var arr = [90,99,95,94,95];
  3. countSort(arr);
  5. function countSort(arr) {
  6.   const __list = [];
  7.   let max = arr[0];
  8.   let min = arr[0];
  9.   for (let i = 0; i < arr.length; i++) {
  10.     if (max < arr[i]) {
  11.        max = arr[i];
  12.     }
  13.     if (min > arr[i]) {
  14.       min = arr[i];
  15.     }
  16.   }
  17.   const len = max - min;
  18.   __list.length = len + 1;
  19.   __list.fill(0);
  21.   for (let i = 0; i < arr.length; i++) {
  22.           __list[arr[i] - min]++;
  23.   }
  24.   for (let i = 1; i < __list.length; i++) {
  25.     __list[i] += __list[i - 1];
  26.   }
  27.   let __newList = [];
  28.   __newList.length = arr.length;
  29.   for (let i = arr.length - 1; i >= 0; i--) {
  30.     __newList[__list[arr[i] - min] - 1] = arr[i]
  31.     __list[arr[i] - min] -= 1;
  32.   }
  33.   console.log(__newList);
  34.   return __newList;
  35. }
  37. // VM3831:35 (5) [90, 94, 95, 95, 99]

桶排序

区间跨度 = （最大值 - 最小值） / （桶的数量 - 1）
1.获取最大值max，最小值min，差值d
2.初始化桶，桶的长度 = arr.length
bucketNum = arr.length
bucketArr = [];
for (let i = 0; i < bucketNum; i++) bucketArr.push([]);
3.遍历元素数组，将每个元素加入对应的桶中
const num = parseInt((max - min) / (bucketNum - 1));
bucketArr[num].push(arr[i])
4.对每个桶内部进行排序 Timsort
bucketArr[i].sort()
5.输出 …

function sort(arr) {
  let max = arr[0];
  let min = arr[0];
  for (let i = 0; i < arr.length; i++) {
    if (max < arr[i]) {
       max = arr[i];
    }
    if (min > arr[i]) {
      min = arr[i];
    }
  }
  const d = max - min;
  const bucketNum = arr.length
  const bucketArr = [];
  for (let i = 0; i < bucketNum; i++)
    bucketArr.push([]);
  for (let i = 0; i < arr.length; i++) {
    const num = parseInt((max - min) / (bucketNum - 1));
    bucketArr[num].push(arr[i])
  }
  for (let i = 0; i < arr.length; i++) {
    bucketArr[i].sort(); // 采用Timsort排序
  }
  const sortArr = [];
  for (let i = 0; i < bucketArr.length; i++) {
    for (let j = 0; j < bucketArr[i].length; j++) {
      sortArr.push(bucketArr[i][j])
    }
  }
  console.log(sortArr);
  return sortArr;
}

var arr = [0.84, 4.5, 2.18, 0.5, 3.25]
sort(arr);
// VM3938:30 (5) [0.5, 0.84, 2.18, 3.25, 4.5]