常见排序算法详解与实现

冒泡排序 (Bubble Sort)#

冒泡排序是最简单直观的排序算法之一。它重复地遍历要排序的数组，比较相邻元素，如果顺序错误则交换它们。这个过程会不断重复，直到没有再需要交换的元素，也就是数组已经排序完成。

时间复杂度: O(n²) - 最坏情况、平均情况 空间复杂度: O(1) 稳定性: 稳定

import { swap } from './swap';

export function bubbleSort(arr: number[]) {
  let swaped = false;
  const length = arr.length;
  for (let j = length; j > 0; j--) {
    for (let i = 1; i < j; i++) {
      if (arr[i - 1] > arr[i]) {
        swaped = true;
        swap(arr, i - 1, i);
      }
    }

    if (!swaped) {
      return;
    }
    swaped = false;
  }
}

选择排序 (Selection Sort)#

选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序区间中找到最小元素，将其放到已排序区间的末尾。算法维护两个子数组：已排序子数组和未排序子数组。

时间复杂度: O(n²) - 最坏情况、平均情况、最好情况 空间复杂度: O(1) 稳定性: 不稳定

import { swap } from './swap';

export function selectionSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    if (i !== min) {
      swap(arr, i, min);
    }
  }
}

插入排序 (Insertion Sort)#

插入排序的工作方式类似于我们整理一手扑克牌。开始时，我们的左手为空，牌面朝下放在桌上。然后，我们每次从桌上拿走一张牌，并将它插入左手中正确的位置。为了找到这个位置，我们从右到左将它与已在手中的牌进行比较。

时间复杂度: O(n²) - 最坏情况、平均情况；O(n) - 最好情况（已排序） 空间复杂度: O(1) 稳定性: 稳定

export function insertion_sort(arr: number[]) {
  for (let j = 1; j < arr.length; j++) {
    const target = arr[j];
    let i = j - 1;
    while (i >= 0 && arr[i] > target) {
      arr[i + 1] = arr[i];
      i--;
    }
    arr[i + 1] = target;
  }
}

希尔排序 (Shell Sort)#

希尔排序是插入排序的一种改进版本。它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。这种方法可以显著减少小元素需要移动的次数。

时间复杂度: 取决于间隔序列，一般为O(n log² n) 空间复杂度: O(1) 稳定性: 不稳定

import { swap } from './swap';

export function shell_sort(nums: number[]) {
  let h = 1;
  const length = nums.length;
  while (h < length / 3) {
    h = h * 3 + 1;
  }

  while (h >= 1) {
    for (let j = h; j < length; j++) {
      for (let i = j; i >= h && nums[i - h] > nums[i]; i = i - h) {
        swap(nums, i, i - h);
      }
    }
    h = Math.floor(h / 3);
  }
  return nums;
}