排序算法是计算机科学中的基本问题之一，广泛应用于各种需要对数据进行排序的场景。不同的排序算法在处理不同类型数据时有各自的优势与劣势。本文将带你了解几种常见的排序算法，包括它们的原理、实现、优缺点，以及它们从简单到复杂的演变过程。

1. 冒泡排序（Bubble Sort）

原理： 冒泡排序通过重复遍历待排序列表，比较相邻元素并交换位置，最终将最大的元素逐步“冒泡”到列表的末尾。

实现代码：

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

优缺点：

• 优点：实现简单，适合小规模数据。
• 缺点：时间复杂度为 O(n²)，在数据规模较大时性能低下。

适用场景： 冒泡排序适合数据量较小的简单场景，或用于教学演示基本排序思想。

2. 选择排序（Selection Sort）

原理： 选择排序每次从未排序部分中选择最小（或最大）的元素，并将其放到已排序部分的末尾。通过不断选择和交换位置逐步完成排序。

实现代码：

function selectionSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

优缺点：

• 优点：减少了交换次数，空间复杂度为 O(1)。
• 缺点：时间复杂度依旧是 O(n²)，效率较低。

适用场景： 选择排序适合数据量较小，且希望通过减少交换次数提高性能的场景。

3. 插入排序（Insertion Sort）

原理： 插入排序通过逐步将每个元素插入到已排序部分的适当位置，类似于打牌时整理手牌的过程。

实现代码：

function insertionSort(arr: number[]): number[] {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

优缺点：

• 优点：对于部分已排序的数据，插入排序的效率较高，且适合在线算法。
• 缺点：时间复杂度为 O(n²)，当数据量较大时性能较差。

适用场景： 插入排序适合数据基本有序的情况，或需要实时处理输入数据的场景。

4. 归并排序（Merge Sort）

原理： 归并排序采用分治法，将数组递归地拆分成较小的子数组，分别进行排序后再合并。每次合并都是将两个有序子数组合并为一个大数组。

实现代码：

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

优缺点：

• 优点：稳定排序，时间复杂度为 O(n log n)，适合处理大规模数据。
• 缺点：空间复杂度较高，为 O(n)，需要额外的存储空间。

适用场景： 归并排序适用于需要稳定排序的大规模数据集，如需要保证数据原有顺序的系统。

5. 快速排序（Quick Sort）

原理： 快速排序也是一种分治算法。通过选择一个“基准”（pivot）元素，将数组分为两部分，使得基准左边的元素都比它小，右边的元素都比它大，然后递归地对两部分进行排序。

实现代码：

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  const equal = arr.filter(x => x === pivot);

  return quickSort(left).concat(equal, quickSort(right));
}

优缺点：

• 优点：平均时间复杂度为 O(n log n)，在大多数情况下性能表现优秀。
• 缺点：最坏情况下时间复杂度为 O(n²)，不稳定排序，递归栈空间消耗较大。

适用场景： 快速排序是大多数情况下的首选排序算法，适合一般性大规模数据排序。

算法性能比较