TypeScript十大排序算法插入排序?qū)崿F(xiàn)示例詳解

更新時間：2023年02月23日 09:56:24 作者：coderwhy

這篇文章主要為大家介紹了TypeScript十大排序算法插入排序?qū)崿F(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

一. 插入排序的定義

插入排序就像是你打撲克牌，你從牌堆頂取一張牌，找到合適的位置插入到已有牌的順序中，并不斷重復這一步驟直到所有的牌都被插入到合適的位置，最終使得整副牌有序。

與打牌類似，插入排序（Insertion sort）的實現(xiàn)方法是：

首先假設第一個數(shù)據(jù)是已經(jīng)排好序的，接著取出下一個數(shù)據(jù)，在已經(jīng)排好序的數(shù)據(jù)中從后往前掃描，找到比它小的數(shù)的位置，將該位置之后的數(shù)整體后移一個單位，然后再將該數(shù)插入到該位置。
不斷重復上述操作，直到所有的數(shù)據(jù)都插入到已經(jīng)排好序的數(shù)據(jù)中，排序完成。

插入排序的優(yōu)勢在于它的性能表現(xiàn)在已經(jīng)有序的序列上比冒泡排序、選擇排序兩種算法要好。

它的時間復雜度為O(n)，因此，如果序列已經(jīng)被排好，插入排序?qū)让芭菖判蚝瓦x擇排序快得多。
另外，插入排序空間復雜度為O(1)，因此，對于內(nèi)存限制較小的情況，插入排序也是一個更優(yōu)的選擇。

二. 插入排序的流程

插入排序的流程如下：

首先，假設數(shù)組的第一個元素已經(jīng)排好序了，因為它只有一個元素，所以可以認為是有序的。
然后，從第二個元素開始，不斷與前面的有序數(shù)組元素進行比較。
如果當前元素小于前面的有序數(shù)組元素，則把當前元素插入到前面的合適位置。
否則，繼續(xù)與前面的有序數(shù)組元素進行比較。
以此類推，直到整個數(shù)組都有序。
循環(huán)步驟2~5，直到最后一個元素。
完成排序。

三. 插入排序的圖解

四. 插入排序的代碼

以下是 TypeScript 實現(xiàn)的插入排序代碼，帶有詳細的注釋：

function insertionSort(arr: number[]): number[] {
  // 對于數(shù)組的每一個元素，從它開始到0位置，比較該元素和前一個元素的大小
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    // 如果該元素小于前一個元素，那么前一個元素向后移動，并繼續(xù)向前比較
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    // 如果該元素大于前一個元素，那么它將放到合適的位置
    arr[j + 1] = current;
  }
  // 返回排序后的數(shù)組
  return arr;
}
// 測試數(shù)據(jù)
const testArr = [5, 2, 9, 1, 5, 6];
// 調(diào)用插入排序函數(shù)
const sortedArr = insertionSort(testArr);
// 打印結(jié)果
console.log(sortedArr);

代碼執(zhí)行的過程：

首先我們定義了一個 insertSort 函數(shù)，并傳入一個數(shù)字數(shù)組作為參數(shù)。
接著我們定義一個變量 current，它將存儲當前需要比較的數(shù)字。
然后我們使用一個循環(huán)，將數(shù)組的第二項到最后一項依次與前面的數(shù)字進行比較。
在內(nèi)層循環(huán)中，我們首先將 j 定義為 i-1，然后每次執(zhí)行循環(huán)時，如果 j 大于等于 0 并且 arr[j] 大于 current，我們就交換 arr[j] 和 arr[j + 1] 的值。
在循環(huán)結(jié)束后，我們將 current 插入到正確的位置，并繼續(xù)比較下一個數(shù)字。
當所有數(shù)字都被比較過后，我們就可以返回最終排序好的數(shù)組。