排序

冒泡排序 O(n^2)

function bubbleSort(array) {
  const length = array.length;

  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // 交换相邻元素的位置
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }

  return array;
}

// 使用示例
const array = [29, 25, 3, 49, 9, 37, 21, 43];
const sortedArray = bubbleSort(array);
console.log(sortedArray); // 输出：[3, 9, 21, 25, 29, 37, 43, 49]

桶排序 O(n+k)

function bucketSort(array, bucketSize) {
  if (array.length === 0) {
    return array;
  }

  // 寻找最大值和最小值
  let minValue = array[0];
  let maxValue = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i];
    } else if (array[i] > maxValue) {
      maxValue = array[i];
    }
  }

  // 计算桶的数量
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);

  // 初始化桶
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }

  // 将元素分配到不同的桶中
  for (let i = 0; i < array.length; i++) {
    const bucketIndex = Math.floor((array[i] - minValue) / bucketSize);
    buckets[bucketIndex].push(array[i]);
  }

  // 对每个桶中的元素进行排序
  const sortedArray = [];
  for (let i = 0; i < bucketCount; i++) {
    insertionSort(buckets[i]); // 可以使用其他排序算法对桶中的元素进行排序，这里使用插入排序作为示例
    sortedArray.push(...buckets[i]); // 将排好序的桶中的元素合并到有序数组中
  }

  return sortedArray;
}

// 插入排序算法
function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    const current = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > current) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = current;
  }
}

// 使用示例
const array = [29, 25, 3, 49, 9, 37, 21, 43];
const sortedArray = bucketSort(array, 5);
console.log(sortedArray); // 输出：[3, 9, 21, 25, 29, 37, 43, 49]

快排序 O(nlogn)

function quickSort(array) {
  if (array.length <= 1) {
    return array; // 如果数组长度小于等于1，直接返回
  }

  const pivotIndex = Math.floor(array.length / 2); // 选择中间元素作为基准
  const pivot = array[pivotIndex]; // 基准元素

  const left = [];
  const right = [];

  for (let i = 0; i < array.length; i++) {
    if (i === pivotIndex) {
      continue; // 跳过基准元素
    }

    if (array[i] < pivot) {
      left.push(array[i]); // 比基准元素小的放在左边数组
    } else {
      right.push(array[i]); // 比基准元素大的放在右边数组
    }
  }

  const sortedLeft = quickSort(left); // 对左边数组进行递归排序
  const sortedRight = quickSort(right); // 对右边数组进行递归排序

  return [...sortedLeft, pivot, ...sortedRight]; // 合并左边排序结果、基准元素、右边排序结果
}

// 使用示例
const array = [29, 25, 3, 49, 9, 37, 21, 43];
const sortedArray = quickSort(array);
console.log(sortedArray); // 输出：[3, 9, 21, 25, 29, 37, 43, 49]