排序算法总结

排序算法

排序算法是计算机科学中最基础的算法之一，它们将一组元素按照一定的规则重新排列。下面是一些常见的排序算法：

1. 冒泡排序（Bubble Sort）：比较相邻的两个元素，如果前一个比后一个大，就交换它们的位置。重复这个过程，直到没有任何一对数字需要交换为止。

2. 插入排序（Insertion Sort）：将数组分为已排序区间和未排序区间，初始时已排序区间只有一个元素，每次将未排序区间中的一个元素插入到已排序区间中的正确位置。

3. 选择排序（Selection Sort）：每次从未排序区间中找到最小（或最大）的元素，将其放到已排序区间的末尾。

4. 快速排序（Quick Sort）：选择一个基准元素，将小于它的元素放在左边，大于它的元素放在右边，然后对它左右两边的子数组分别递归地进行同样的操作。

5. 归并排序（Merge Sort）：将数组分成两个子数组，分别递归地进行排序，然后将两个子数组合并成一个有序的数组。

6. 堆排序（Heap Sort）：将数组构建成一个堆，然后不断将堆顶元素与堆底元素交换，并重新调整堆，直到整个数组变成有序的。

7. 希尔排序（Shell Sort）：将数组按照一定的间隔分组，对每组进行插入排序，然后逐步缩小间隔直到变为 1，最后进行一次插入排序。

下表列出了以上排序算法的时间复杂度和空间复杂度，以及使用场景：

算法名称	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性	使用场景
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	适用于小数据量或已经接近有序的数据
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	适用于小数据量或已经接近有序的数据
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	适用于小数据量
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(logn)~O(n)	不稳定	适用于中等大小数据量
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定	适用于大数据量
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定	适用于大数据量
希尔排序	O(nlogn)~O(n^2)	O(n^2)	O(n)	O(1)	不稳定	适用于中等大小数据量

注意：时间复杂度中的 n 是指数组的长度。空间复杂度中的 O(logn)~O(n) 表示递归调用所需要的空间，取决于递归深度，最好情况下是 O(logn)，最坏情况下是 O(n)。稳定性指排序算法是否能够保证相等元素的相对顺序不变。

冒泡排序

下面是使用 TypeScript 实现冒泡排序的代码：

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

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = bubbleSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. bubbleSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 内部使用两层循环来实现冒泡排序。外层循环控制排序的轮数，内层循环控制每轮排序中相邻元素的比较和交换。

3. 如果相邻元素的顺序不正确，就交换它们的位置。

4. 最后返回排序后的数组。

插入排序

下面是使用 TypeScript 实现插入排序的代码：

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

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = insertionSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. insertionSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 外层循环从数组的第二个元素开始，依次将其插入前面已排序的子数组中。

3. 内层循环从当前元素的前一个元素开始，依次与当前元素比较，如果前一个元素大于当前元素，则将前一个元素后移一位。

4. 当找到第一个小于等于当前元素的元素时，将当前元素插入其后面。

5. 重复执行步骤 2~4，直到整个数组都被排序好。

6. 最后返回排序后的数组。

选择排序

下面是使用 TypeScript 实现选择排序的代码：

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

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = selectionSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. selectionSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 外层循环从数组的第一个元素开始，依次选择最小的元素并将其与当前元素交换位置。

3. 内层循环从当前元素的下一个元素开始，依次与当前元素比较，找到最小的元素的下标。

4. 如果最小元素的下标不是当前元素的下标，则将这两个元素交换位置。

5. 重复执行步骤 2~4，直到整个数组都被排序好。

6. 最后返回排序后的数组。

快速排序

下面是使用 TypeScript 实现快速排序的代码：

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) {
    return arr; // 基线条件：数组长度为 0 或 1，直接返回
  }
  const pivot = arr[0]; // 选择第一个元素作为基准值
  const leftArr = [];
  const rightArr = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      leftArr.push(arr[i]);
    } else {
      rightArr.push(arr[i]);
    }
  }
  return [...quickSort(leftArr), pivot, ...quickSort(rightArr)]; // 递归调用
}

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = quickSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. quickSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 首先检查数组长度是否为 0 或 1，如果是，则直接返回原数组。这是递归算法的基线条件。

3. 选择数组的第一个元素作为基准值（pivot）。

4. 将数组中剩余的元素分别与基准值比较，小于基准值的元素放入左侧数组（leftArr），大于等于基准值的元素放入右侧数组（rightArr）。

5. 对左侧数组和右侧数组分别递归调用 quickSort 函数，将结果合并。

6. 最后返回合并后的数组。

注意：以上代码中的 number 类型可以根据实际情况替换成其他类型。此外，以上代码实现了简单版本的快速排序，还有其他变种的快速排序算法，例如随机化快速排序、三路快速排序等，可以根据具体情况选择使用。

归并排序

下面是使用 TypeScript 实现归并排序的代码：

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) {
    return arr; // 基线条件：数组长度为 0 或 1，直接返回
  }
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);
  return merge(mergeSort(leftArr), mergeSort(rightArr)); // 递归调用
}

function merge(leftArr: number[], rightArr: number[]): number[] {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      result.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }
  return result.concat(leftArr.slice(leftIndex), rightArr.slice(rightIndex));
}

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. mergeSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 首先检查数组长度是否为 0 或 1，如果是，则直接返回原数组。这是递归算法的基线条件。

3. 将数组分成两个子数组（leftArr 和 rightArr），分别递归调用 mergeSort 函数。

4. 调用 merge 函数将左侧数组和右侧数组合并成一个数组。

5. 重复执行步骤 2~4，直到整个数组都被排序好。

6. 最后返回排序后的数组。

7. merge 函数接受两个已排序的数组作为参数，返回一个合并后的已排序数组。

8. 在 merge 函数中，使用两个指针（leftIndex 和 rightIndex）分别指向左侧数组和右侧数组的开头，比较两个指针所指向的元素大小，将较小的元素加入结果数组（result）中。

9. 当其中一个数组被遍历完后，将另一个数组剩余的元素加入结果数组中。

10. 最后返回合并后的已排序数组。

归并排序的时间复杂度为 O(nlogn)，是一种比较高效的排序算法。

堆排序

下面是使用 TypeScript 实现堆排序的代码：

function heapSort(arr: number[]): number[] {
  buildMaxHeap(arr); // 构建最大堆
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 将堆顶元素与末尾元素交换
    maxHeapify(arr, 0, i); // 对剩余元素重新构建最大堆
  }
  return arr;
}

function buildMaxHeap(arr: number[]): void {
  const len = arr.length;
  const lastParentIndex = Math.floor(len / 2) - 1; // 最后一个非叶子节点的下标
  for (let i = lastParentIndex; i >= 0; i--) {
    maxHeapify(arr, i, len); // 对每个非叶子节点进行最大堆化
  }
}

function maxHeapify(arr: number[], index: number, heapSize: number): void {
  const leftIndex = index * 2 + 1;
  const rightIndex = index * 2 + 2;
  let largestIndex = index;
  if (leftIndex < heapSize && arr[leftIndex] > arr[largestIndex]) {
    largestIndex = leftIndex;
  }
  if (rightIndex < heapSize && arr[rightIndex] > arr[largestIndex]) {
    largestIndex = rightIndex;
  }
  if (largestIndex !== index) {
    [arr[index], arr[largestIndex]] = [arr[largestIndex], arr[index]]; // 交换元素
    maxHeapify(arr, largestIndex, heapSize); // 递归调用，对被交换的子树进行最大堆化
  }
}

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = heapSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. heapSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 首先调用 buildMaxHeap 函数构建最大堆。

3. 从数组末尾开始，依次将堆顶元素（最大元素）与末尾元素交换位置。

4. 对剩余的元素重新构建最大堆。

5. 重复执行步骤 3~4，直到整个数组都被排序好。

6. 最后返回排序后的数组。

7. buildMaxHeap 函数接受一个数字数组作为参数，用于构建最大堆。

8. 首先计算出最后一个非叶子节点的下标。

9. 从最后一个非叶子节点开始，依次对每个非叶子节点进行最大堆化。

10. maxHeapify 函数接受一个数字数组、一个下标和堆的大小作为参数，用于最大堆化。

11. 首先计算出左右子节点的下标，并将当前节点设为最大节点。

12. 如果左子节点的值比最大节点的值大，则将左子节点设为最大节点。

13. 如果右子节点的值比最大节点的值大，则将右子节点设为最大节点。

14. 如果最大节点不是当前节点，则交换当前节点和最大节点的值，并对被交换的子树进行最大堆化。

15. 重复执行步骤 11~14，直到整个子树都被最大堆化。

堆排序的时间复杂度为 O(nlogn)，是一种比较高效的排序算法。

希尔排序

下面是使用 TypeScript 实现希尔排序的代码：

function shellSort(arr: number[]): number[] {
  const len = arr.length;
  let gap = Math.floor(len / 2); // 初始步长
  while (gap > 0) {
    // 插入排序
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let j = i - gap;
      while (j >= 0 && arr[j] > temp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = temp;
    }
    gap = Math.floor(gap / 2); // 缩小步长
  }
  return arr;
}

// 使用示例
const arr = [5, 3, 8, 4, 2];
const sortedArr = shellSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

解释：

1. shellSort 函数接受一个数字数组作为参数，返回排序后的数组。

2. 首先计算出数组长度和初始步长（通常为数组长度的一半）。

3. 对于每个步长，执行一次插入排序。

4. 插入排序的实现方式与普通插入排序相同，只是将增量值（步长）作为循环变量的步长。

5. 每完成一次插入排序后，将步长缩小为原来的一半。

6. 重复执行步骤 3~5，直到步长为 1。

7. 最后返回排序后的数组。

希尔排序的时间复杂度为 O(nlogn)，是一种比较高效的排序算法。