typescript sort|极客笔记

typescript sort

1. 介绍

在计算机科学中，排序是一种将一组元素按照特定顺序排列的操作。排序算法可以应用于各种领域，包括数据库查询，图形图像处理和算法设计等。在本文中，我将介绍几种常见的排序算法，并使用Typescript语言实现它们。

2. 冒泡排序

冒泡排序是最简单的排序算法之一。它重复地遍历待排序的元素，并比较相邻的元素。如果它们的顺序不正确，就将它们交换。该算法的时间复杂度为O(n^2)。

示例代码：

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

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = bubbleSort(unsortedArray);
console.log(sortedArray); // 输出 [11, 12, 22, 25, 34, 64, 90]

3. 插入排序

插入排序的基本思想是将待排序的元素逐个插入到已排序的列表中。它从列表的第二个元素开始，将该元素与已排序的元素进行比较并插入正确的位置。该算法的时间复杂度为O(n^2)，但在最好的情况下，即列表已经部分排序的情况下，时间复杂度可以降为O(n)。

示例代码：

function insertionSort(arr: number[]): number[] {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    const 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;
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = insertionSort(unsortedArray);
console.log(sortedArray); // 输出 [11, 12, 22, 25, 34, 64, 90]

4. 选择排序

选择排序是一种简单直观的排序算法。它重复地选择数组中最小（或最大）的元素，并将其放在已排序序列的末尾。与冒泡排序不同，选择排序每次遍历都只交换一次元素。该算法的时间复杂度为O(n^2)。

示例代码：

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;
      }
    }
    const temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // 输出 [11, 12, 22, 25, 34, 64, 90]

5. 快速排序

快速排序是一种高效的排序算法，它使用分治的思想。它选择一个基准元素（通常是数组的第一个或最后一个元素），并将数组分割为两个子数组：小于基准元素的元素和大于基准元素的元素。然后，对这两个子数组递归地应用快速排序。该算法的时间复杂度为O(nlogn)。

示例代码：

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

  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];

  for (const num of arr) {
    if (num < pivot) {
      left.push(num);
    } else {
      right.push(num);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // 输出 [11, 12, 22, 25, 34, 64, 90]

6. 归并排序

归并排序是一种基于分治思想的排序算法。它将数组拆分为越来越小的子数组，再将子数组合并为排序好的数组。该算法的时间复杂度为O(nlogn)。

示例代码：

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

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

  const merge = (left: number[], right: number[]): number[] => {
    const merged: number[] = [];
    let i = 0;
    let j = 0;

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

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

  return merge(mergeSort(left), mergeSort(right));
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray); // 输出 [11, 12, 22, 25, 34, 64, 90]