JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

// 桶排序
const bucketSort = (array, bucketSize) => {
  if (array.length === 0) {
    return array;
  }
  console.time('桶排序耗时');
  let i = 0;
  let minValue = array[0];
  let maxValue = array[0];
  for (i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i]; //输入数据的最小值
    } else if (array[i] > maxValue) {
      maxValue = array[i]; //输入数据的最大值
    }
  }
  //桶的初始化
  const DEFAULT_BUCKET_SIZE = 5; //设置桶的默认数量为 5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  //利用映射函数将数据分配到各个桶中
  for (i = 0; i < array.length; i++) {
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
  }
  array.length = 0;
  for (i = 0; i < buckets.length; i++) {
    quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序
    for (var j = 0; j < buckets[i].length; j++) {
      array.push(buckets[i][j]);
    }
  }
  console.timeEnd('桶排序耗时');
  return array;
};
// 快速排序
const quickSort = (arr, left, right) => {
    let len = arr.length,
        partitionIndex;
    left = typeof left != 'number' ? 0 : left;
    right = typeof right != 'number' ? len - 1 : right;
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};
const partition = (arr, left, right) => {
    //分区操作
    let pivot = left, //设定基准值（pivot）
        index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};
const swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log('原始array:', array);
const newArr = bucketSort(array);
console.log('newArr:', newArr);
// 原始 array:  [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// 堆排序耗时:   0.133056640625ms
// newArr:       [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]

const countingSort = array => {
    let len = array.length,
        result = [],
        countArr = [],
        min = (max = array[0]);
    console.time('计数排序耗时');
    for (let i = 0; i < len; i++) {
        // 获取最小，最大 值
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        countArr[array[i]] = countArr[array[i]] ? countArr[array[i]] + 1 : 1;
    }
    console.log('countArr :', countArr);
    // 从最小值 -> 最大值,将计数逐项相加
    for (let j = min; j < max; j++) {
        countArr[j + 1] = (countArr[j + 1] || 0) + (countArr[j] || 0);
    }
    console.log('countArr 2:', countArr);
    // countArr 中,下标为 array 数值，数据为 array 数值出现次数；反向填充数据进入 result 数据
    for (let k = len - 1; k >= 0; k--) {
        // result[位置] = array 数据
        result[countArr[array[k]] - 1] = array[k];
        // 减少 countArr 数组中保存的计数
        countArr[array[k]]--;
        // console.log("array[k]:", array[k], 'countArr[array[k]] :', countArr[array[k]],)
        console.log('result:', result);
    }
    console.timeEnd('计数排序耗时');
    return result;
};

const array = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log('原始 array: ', array);
const newArr = countingSort(array);
console.log('newArr: ', newArr);
// 原始 array:  [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
// 计数排序耗时:   5.6708984375ms
// newArr:       [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

const countingSort2 = (arr, maxValue) => {
    console.time('计数排序耗时');
    maxValue = maxValue || arr.length;
    let bucket = new Array(maxValue + 1),
        sortedIndex = 0;
    (arrLen = arr.length), (bucketLen = maxValue + 1);
    for (let i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
    for (let j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    console.timeEnd('计数排序耗时');
    return arr;
};

const array2 = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log('原始 array2: ', array2);
const newArr2 = countingSort2(array2, 21);
console.log('newArr2: ', newArr2);
// 原始 array:  [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
// 计数排序耗时:   0.043212890625ms
// newArr:       [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

/**
    * name: 基数排序
    * @param  array 待排序数组
    * @param  max 最大位数
    */
const radixSort = (array, max) => {
    console.time('计数排序耗时');
    const buckets = [];
    let unit = 10,
        base = 1;
    for (let i = 0; i < max; i++, base *= 10, unit *= 10) {
        for (let j = 0; j < array.length; j++) {
            let index = ~~((array[j] % unit) / base); //依次过滤出个位，十位等等数字
            if (buckets[index] == null) {
                buckets[index] = []; //初始化桶
            }
            buckets[index].push(array[j]); //往不同桶里添加数据
        }
        let pos = 0,
            value;
        for (let j = 0, length = buckets.length; j < length; j++) {
            if (buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                    array[pos++] = value; //将不同桶里数据挨个捞出来，为下一轮高位排序做准备，由于靠近桶底的元素排名靠前，因此从桶底先捞
                }
            }
        }
    }
    console.timeEnd('计数排序耗时');
    return array;
};

const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log('原始array:', array);
const newArr = radixSort(array, 2);
console.log('newArr:', newArr);
// 原始 array:  [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
// 堆排序耗时:   0.064208984375ms
// newArr:       [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]