排序算法

1. 冒泡排序

function bubbleSort(arr){
  const {length} = arr;
  for(let i=0;i<length;i++){
    for(let j=0; j<length-1-i;j++) {
      if(arr[j+1]<arr[j]) {
        [arr[j+1], arr[j]] = [arr[j], arr[j+1]]
      }
    }
  }
  return arr;
}
arr = [5,4,3,2,1]
bubbleSort(arr);  //[1,2,3,4,5]

2.选择排序（每次选最小值的index）

function selectionSort(arr) {
    const { length } = arr;
    let indexMin;
    for (let i = 0; i < length; i++) {
        indexMin = i;
        for (let j = i; j < length; j++) {
            if (arr[j] < arr[indexMin]) {
                indexMin = j;
            }
        }
        [arr[indexMin], arr[i]] = [arr[i], arr[indexMin]];
    }
    return arr;
}

arr = [5, 4, 3, 2, 1];
selectionSort(arr);

3.插入排序

function insertionSort(arr) {
    const { length } = arr;
    let tmp;
    for (let i = 1; i < length; i++) {
        let j = i;
        tmp = arr[j];
        while (j > 0 && tmp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = tmp;
    }
    return arr;
}
arr = [5, 4, 3, 2, 1];
insertionSort(arr);

4.归并排序

function mergeSort(arr) {
    const {length} = arr;
    if(length > 1) {
        const middle = Math.floor(length / 2); //取中位index
        const left = mergeSort(arr.slice(0, middle)); //排序左边
        const right = mergeSort(arr.slice(middle));  //排序右边
        arr = merge(left, right) //合并结果
    }
    return arr
}
//归并函数
function merge(left, right) {
    let i=0;
    let j=0;
    const result = [];
    while(i<left.length && j<right.length){
        result.push(left[i]>right[j] ? right[j++] : left[i++])
    }
    return result.concat(i<left.length ? left.slice(i) : right.slice(j))
}

5. 快速排序

function quickSort(arr) {
  return quick(arr, 0, arr.length - 1);
}
function quick(arr, left, right) {
  let index;
  if (arr.length > 1) {
    index = partition(arr, left, right); //先以一个主元排序一次，并且返回这次排序的主元index
    if (left < index - 1) {
      quick(arr, left, index - 1);
    }
    if (right > index) {
      quick(arr, index, right);
    }
  }
  return arr;
}
function partition(arr, left, right) {
  let pivot = arr[Math.floor((left + right) / 2)];
  while (left <= right) {
    while (arr[left] < pivot) {
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }
    if (left <= right) {
      [arr[right], arr[left]] = [arr[left], arr[right]];
      left++;
      right--;
    }
  }
  return left;
}

6.计数排序（只能排正整数）

function countingSort(arr) {
  const maxValue = Math.max(...arr);
  const result = Array(maxValue + 1);
  arr.forEach((item) => {
    if (!result[item]) {
      result[item] = 0;
    }
    result[item]++;
  });
  let sortIdx = 0;
  result.forEach((count, i) => {
    while (count > 0) {
      arr[sortIdx++] = i;
      count--;
    }
  });
  return arr;
}

7.桶排序（用于排序正整数）

function bucketSort(arr, bucketSize) { //可以传入每个桶的容量
  if (arr.length < 2) {
    return arr;
  }
  let buckets = createBuckets(arr, bucketSize);  //生成一个二维数组， [[2,3,1],[8,6,4]]... 最内层是原始元素，第二层是每个生成的桶
  return sortBuckets(buckets); // 将小桶合并为大的数组，即排序后的数组
}

function createBuckets(arr, bucketSize) { // 基本原理是，按一定的值区间，将源数组分成多个（最大值区间除以你传入的桶容量）小桶，而分别排序小桶
  let minValue = arr[0];
  let maxValue = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (minValue > arr[i]) {
      minValue = arr[i];
    }
    if (maxValue < arr[i]) {
      maxValue = arr[i];
    }
  }
  const buckets = Array(
    Math.floor((maxValue - minValue) / bucketSize + 1)
  ).fill([]);
  for (let i = 0; i < arr.length; i++) {
    const bucketIdx = Math.floor((arr[i] - minValue) / bucketSize);
    buckets[bucketIdx].push(arr[i]);
    insertionSort(buckets[buckIdx]);  //这里再利用之前写的插入排序，排序每隔小桶
  }
  return buckets;
}
function sortBuckets(buckets) {
  return buckets.flat();
}