演算法知識 - insertion sort 插入排序

Insertion sort 插入排序 介紹與實作原理

插入排序是最簡單的一種排序法之一，以遞減排序為例。

• 先給定一陣列，index 1 是最大，之後的陣列數值遞減
• 透過雙重迴圈
  • 第一層迴圈，決定第 i 大的位置的數字
  • 第二層迴圈，判斷從第 i 以後的的位置，哪個數字最大就放置後面

時間複查度為 \(O(n^2)\)，雖然不實用，但對初學者直觀

Insertion Sort 程式碼說明與應用

主要核心是

• i 迴圈，數列 i 要被放置哪個位置
• j 迴圈，找出第 (i+1)~n 的數值中，哪個數字最大

由於我們 i 從 0 開始，只要我們每一個 i 都放入 i~n 的最大值，那麼第 i 的數值一定會比 i+1 還大，以此類推，證明這是有效的排序。

下面主要示範由大到小排序

#include <iostream>

using namespace std;
int num[] = {4,96,1546,13,48,34,77,48,31}; //要交換的數列
int num_size; //要排序的數列大小

void insert_sort(){
    num_size = sizeof(num) / sizeof(num[0]); //判斷數列長度
    for(int i = 0; i < num_size; i++){ //判斷第 i 個位置，要放哪個數值，
        for(int j = i+1; j < num_size; j++){ //判斷從 i~n，哪個數字最大
            if(num[i] < num[j]) swap(num[i], num[j]);
        }
    }
}

void output(){ //輸出資料用
    for(int i = 0; i < num_size; i++) cout << num[i] << ' ';
    cout << '\n';
}

int main()
{
    insert_sort();
    output();
    return 0;
}

心得

由於 C++ 已經有很多 sort 套件了，因此我在高中學會後我就再也沒有去複習這些知識。

剛好現在上課有用到那就來複習，順便把它寫出邏輯八！

程式執行結果