目錄

• 一. 插入排序的定義
• 二. 插入排序的流程
• 三. 插入排序的圖解
• 四. 插入排序的代碼
• 五. 插入排序的時間復雜度
• 六. 插入排序的總結

一. 插入排序的定義

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

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

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

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

• 它的時間復雜度為O(n)，因此，如果序列已經被排好，插入排序將會比冒泡排序和選擇排序快得多。
• 另外，插入排序空間復雜度為O(1)，因此，對于內存限制較小的情況，插入排序也是一個更優(yōu)的選擇。

二. 插入排序的流程

插入排序的流程如下：

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

三. 插入排序的圖解

四. 插入排序的代碼

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

function insertionSort(arr: number[]): number[] {  // 對于數組的每一個元素，從它開始到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;  }  // 返回排序后的數組  return arr;}// 測試數據const testArr = [5, 2, 9, 1, 5, 6];// 調用插入排序函數const sortedArr = insertionSort(testArr);// 打印結果console.log(sortedArr);

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

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

五. 插入排序的時間復雜度

插入排序的時間復雜度在最好的情況下為O(n)，在最壞的情況下為O(n^2)，平均時間復雜度為O(n^2)。

當數據已經有序時，插入排序只需要做n-1次比較和0次移動，運行時間為O(n)；

當數據完全逆序時，插入排序需要做n-1趟比較和3/2*(n-1)^2/2次移動，運行時間為O(n^2)。

由于插入排序的最好時間復雜度與最壞時間復雜度都接近O(n^2)，所以插入排序適用于數據規(guī)模不大的場合，如果數據規(guī)模很大，通常使用其他算法。

六. 插入排序的總結

• 插入排序是一種簡單而直觀的排序算法，它可以快速地對部分有序的數組進行排序。
• 插入排序通過比較相鄰的元素并在需要時將其交換，來實現從小到大的排列。
• 插入排序的時間復雜度在最好情況下是線性O(n)，最壞情況下是O(n^2)。

總而言之，如果數組部分有序，插入排序可以比冒泡排序和選擇排序更快。

• 但是如果數組完全逆序，則插入排序的時間復雜度比較高，不如快速排序或歸并排序。
• 因此，在選擇排序算法時，應該根據需要選擇合適的算法。

以上就是TypeScript十大排序算法插入排序實現示例詳解的詳細內容，更多關于TypeScript插入排序算法的資料請關注其它相關文章！