前言：上一篇結束了搜尋的部分，終於進入到鐵人賽的最後一哩路了，之後的篇幅大概會介紹排序法的各個種類，今天就先來講解插入排序法

在進入正題之前，先來說明一下排序的基礎
資料 (Data)：只收集好但沒有經過整理和分析的原始數據，也可稱為資料的原始型態。電腦會將資料儲存成檔案，檔案是一種有組織的資料，各種不同的資料組織稱為資料階層。

資料階層 (Data Hierarchy)
可分為6個階層，最小的存取單位是位元(8個位元唯一個位元組)，數個位元組結合成一個欄位，多個欄位組成紀錄，最後再將一組紀錄存成檔案。

排序的方法：排序主要是處理資料階層檔案中的紀錄，一紀錄的某些欄位稱為鍵值(key)，以特定規則排列成的曾獲遞減順序。也就是說，排序的工作就是執行鍵值得比較和交換，使得鍵值的順序能重新排列。

排序的種類：可分為內部排序法(Internal Sorting)和外部排序法(External Sorting)兩種。內部排序法是將鍵值儲存在電腦記憶體來執行排序；外部排序法因為鍵值的資料量大，無法全部儲存在記憶體，所以排序過程需要使用到外部儲存裝置(例如硬碟等)。
這系列主要都是實作內部排序法居多。

排序的分類標準：

執行效率 (Computational Complexity)
使用時間複雜度常用的Big-O來評估執行效率，範圍大約是從O(n log n)到O(n^2)。

記憶體的使用 (Memory Usage)
排序演算法所要用到的電腦資源，主要是指額外的記憶體空間。

穩定性 (Stability)
指在排序完成後，重複的鍵值順序並不會改變，依然保持原順序。
例如：1號同學A和2號同學B的成績(鍵值)都是82，在排序後不會交換到資料，所以查詢1號依舊會是A同學，不會變為B同學。

氣泡排序法：

可以說是最出名也是相對簡單的排序法了，做法非常容易記住，只需將一串數組的相鄰鍵值進行比較，鍵值較小的就往前移，鍵值較大的就往後挪，直到沒有辦法再移動，就完成了。

執行效率分析：以最懷的情況來看，資料完全是相反的排序，總共需花 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 次，取最高項次n^2，所以執行效率為O(n^2)。
氣泡排序不需要額外的記憶體，屬於穩定性的排序法，因為鍵值在比較，相同鍵值的元素並不會交換。

實作練習：

結果出來了，跟預期的一樣！

也可以將原素轉換的過程印出來，這樣也比較清楚真正的運作方式。

將每次轉換的結果記錄下來，結果如下。

但其實這樣的方法不是最有效率的，假如有一段數列已經符合排序了(例如上圖第四行的56,61,76,88)，但是現在寫的程式碼依然會檢查那段有沒有符合，這樣會影響程式執行的效率，所以還能再修改一下程式碼。

這樣也會得到相同的結果，雖然這只是小程式不會有太大差別，但還是養成習慣會比較好喔！

本日小結：今天帶大家認識排序法的入門階段，講解完基礎觀念和實作一個氣泡排序也花了不少時間，不過繁瑣的定義已經結束了，下一篇開始會開始有比較多練習，大家加油୧༼✿ ͡◕ д ◕͡ ༽୨

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const vector<T>& vec) { //編寫print函式，印出結果
	for (auto e : vec)
		std::cout << e << " ";
	std::cout << endl;
}

template <typename T>
void Swap(T& a, T& b) { //編寫兩兩元素交換的方法
	T t = a;
	a = b;
	b = t;
}

template <typename T>
void bubble_sort(vector<T> & a) { //編寫氣泡排序
	for (int i = a.size() - 1; i > 0; i--) {
		bool swaped = false; //先建立bool類型的變數
		for (int j = 0; j < i; j++)
			if (a[j + 1] < a[j]) {
				Swap(a[j], a[j + 1]);
				swaped = true; //當有交換發生，將swaped改為true
			}
				
		print(a);
		if (!swaped) break; //若這次迴圈沒有交換到，代表之後的元素已排序好，可以直接退出迴圈
	}
}

主程式碼有許多方法可以呈現，這裡就不放上來了，還是不清楚怎麼操作的參考文章內的圖片