TypeScript 陣列的归并排序(mergeSort)

TypeScript 是一種 JavaScript 的超集，它擁有更多的特性，可以讓開發者更容易開發出更優質的程式碼。其中一個特性就是支援归并排序，也就是 mergeSort，它是一種分治演算法，可以將一個陣列分成兩個子陣列，並對兩個子陣列分別排序，最後再將兩個子陣列合併成一個有序的陣列。

實作 mergeSort

要實作 mergeSort，首先要先定義一個函式，該函式接收一個陣列作為參數，並將該陣列分成兩個子陣列，然後對兩個子陣列分別排序，最後再將兩個子陣列合併成一個有序的陣列。

function mergeSort(arr: number[]) {
  // 如果陣列長度小於等於 1，則直接回傳
  if (arr.length <= 1) {
    return arr;
  }

  // 將陣列分成兩個子陣列
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // 對兩個子陣列分別排序
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // 將兩個子陣列合併成一個有序的陣列
  return merge(sortedLeft, sortedRight);
}

接著，我們還需要定義一個函式，該函式接收兩個有序的陣列作為參數，並將兩個陣列合併成一個有序的陣列。

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

  // 將兩個陣列中的元素逐一比較，將較小的元素放入 result 陣列中
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 將剩餘的元素放入 result 陣列中
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

實際應用

我們可以使用 mergeSort 來對陣列進行排序，例如，我們可以對一個數字陣列進行排序：

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

我們也可以對一個字串陣列進行排序：

const arr = ["apple", "banana", "orange", "pear"];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // ["apple", "banana", "orange", "pear"]

總結

TypeScript 支援归并排序，也就是 mergeSort，它是一種分治演算法，可以將一個陣列分成兩個子陣列，並對兩個子陣列分別排序，最後再將兩個子陣列合併成一個有序的陣列。我們可以使用 mergeSort 來對陣列進行排序，無論是數字陣列還是字串陣列，都可以使用 mergeSort 來對陣列進行排序。

Categorized in:

TypeScript

Tagged in: