记录-前端基础之10种排序算法

function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i; // 先假设当前位置是最小值的索引
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { // 如果后面的元素比当前最小值还要小，更新最小值的索引
        minIndex = j;
      }
    }
    var temp = arr[minIndex]; // 将最小值与当前位置交换
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

function countingSort(arr) {
  var len = arr.length;
  var max = Math.max.apply(null, arr); // 找到最大值
  var min = Math.min.apply(null, arr); // 找到最小值
  var count = new Array(max - min + 1).fill(0); // 创建一个计数数组，初始值为0
  var output = new Array(len); // 创建一个与原数组长度相同的输出数组
  for (var i = 0; i < len; i++) {
    count[arr[i] - min]++; // 计数数组中对应元素的计数加1
  }
  for (var j = 1; j < count.length; j++) {
    count[j] += count[j-1]; // 将计数数组进行累加，得到每个元素的最终位置
  }
  for (var k = len-1; k >= 0; k--) {
    output[count[arr[k]-min]-1] = arr[k]; // 将当前元素放到对应位置，并将计数数组中对应元素的计数减1
    count[arr[k]-min]--;
  }
  for (var m = 0; m < len; m++) {
    arr[m] = output[m]; // 将输出数组复制回原数组
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(countingSort(arr));

function bucketSort(arr, bucketSize) {
  if (arr.length === 0) { // 如果数组为空，直接返回
    return arr;
  }
  var i;
  var minValue = arr[0]; // 找到数组中的最小值和最大值
  var maxValue = arr[0];
  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }
  var DEFAULT_BUCKET_SIZE = 5; // 设置默认的桶大小为5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; // 如果未指定桶大小，使用默认大小
  var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; // 计算需要的桶的数量
  var buckets = new Array(bucketCount); // 创建桶数组
  for (i = 0; i < buckets.length; i++) { // 初始化桶数组
    buckets[i] = [];
  }
  for (i = 0; i < arr.length; i++) { // 将元素分配到桶中
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }
  arr.length = 0; // 将原数组清空
  for (i = 0; i < buckets.length; i++) { // 对每个桶进行插入排序，并将它们合并到原数组中
    insertionSort(buckets[i]);
    for (var j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }
  return arr; // 返回排序后的数组
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bucketSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

function radixSort(arr) {
  var maxDigit = getMaxDigit(arr);
  for (var i = 0; i < maxDigit; i++) {
    arr = bucketSort(arr, i);
  }
  return arr;
}

// 获取数组中最大数字的位数
function getMaxDigit(arr) {
  var maxDigit = 1;
  for (var i = 0; i < arr.length; i++) {
    var num = arr[i];
    var digit = 1;
    while (Math.floor(num/10) !== 0) {
      digit++;
      num = Math.floor(num/10);
    }
    if (digit > maxDigit) {
      maxDigit = digit;
    }
  }
  return maxDigit;
}

// 根据数字的某一位进行桶排序
function bucketSort(arr, digit) {
  var buckets = new Array(10); // 创建10个桶
  for (var i = 0; i < buckets.length; i++) {
    buckets[i] = []; // 初始化每个桶
  }
  for (var j = 0; j < arr.length; j++) {
    var num = arr[j];
    var radix = getRadix(num, digit); // 获取数字的某一位
    buckets[radix].push(num); // 将数字放入对应的桶中
  }
  var result = [];
  for (var k = 0; k < buckets.length; k++) { // 将所有桶中的数字按顺序放入结果数组中
    result = result.concat(buckets[k]);
  }
  return result;
}

// 获取数字的某一位
function getRadix(num, digit) {
  return Math.floor(num / Math.pow(10, digit)) % 10;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(radixSort(arr));