冒泡排序

时间复杂度 O(n^2) 空间复杂度 O(1)

function bubbleSort(arr) {
  // 外层循环控制每次排序的轮数
  for (let i = 0; i < arr.length - 1; i++) {
    // 内层循环控制每次排序的比较和交换
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 如果前一个元素大于后一个元素，则交换它们的位置
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// 示例
const arr = [3, 1, 6, 2, 8, 5];
console.log(bubbleSort(arr)); // 输出 [1, 2, 3, 5, 6, 8]

选择排序

时间复杂度 O(n^2) 空间复杂度 O(1)

function selectSort(nums) {
    let len = nums.length;

    // 最后一轮只有一个元素，一定是最大的元素，因此写 i < len - 1
    for (let i = 0; i < len - 1; i++) {

        // 在 [i + 1, len - 1] 区间里选择最小的元素的下标
        // 这种一趟扫描选出最值的方法，有一个很形象的名字叫：打擂台算法
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }

        // 将最小的元素交换到未排序的第一项
        [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }

    return nums;
}

插入排序

时间复杂度 O(n^2) 空间复杂度 O(1)

let insertionSort = function (nums) {
    let len = nums.length;

    // 1. 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
    for (let i = 1; i < len; i++) {
        // 2. 从后向前逐个交换，直到前面的那个元素小于或者等于当前要插入的这个元素
        for (let j = i; j > 0; j--) {
            if (nums[j - 1] > nums[j]) {
                [nums[j - 1], nums[j]] = [nums[j], nums[j - 1]]; // 交换位置
            } else {
                break; // 插入后无需再比较，跳出循环
            }
        }
    }

    return nums;
}

---

希尔排序

时间复杂度 O(nlogn) 空间复杂度 O(1)

归并排序

时间复杂度 O(nlogn) 空间复杂度 O(n)

function mergeSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
   // 分
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    // 合
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    
    while (left.length) {
        result.push(left.shift());
    }
    
    while (right.length) {
        result.push(right.shift());
    }
    
    return result;
}

var arr = [6, 1, 4, 7, 3, 8, 2, 5];
console.log(mergeSort(arr)); // 输出: [ 1, 2, 3, 4, 5, 6, 7, 8 ]

快速排序

时间复杂度 O(nlogn) 空间复杂度 O(logn)

function quickSort(arr) {
  if (arr.length < 2) {
    return arr
  }

  const mid = arr[0]
  const left = []
  const right = []

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < mid) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  return quickSort(left).concat(mid, quickSort(right))
}

var arr = [6, 1, 4, 7, 3, 8, 2, 5]
console.log(quickSort(arr)) // 输出: [ 1, 2, 3, 4, 5, 6, 7, 8 ]

堆排序

时间复杂度 O(nlogn) 空间复杂度 O(1)

---