//⒈ 從第一個元素開始，該元素可以認為已經被排序
//⒉ 取出下一個元素，在已經排序的元素序列中從后向前掃描
//⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
//⒋ 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
//⒌ 將新元素插入到下一位置中
//⒍ 重復步驟2~5

include<iostream>
include<array>
using namespace std;
template<class T>
void insertion_sort(T&, int);
int main()
{
array<int, 10> arr={1,3,2,5,4,6,8,7,9,0};
insertion_sort(arr, arr.size()); //輸入數組和數組大小，因為array是類，所以我們沒法拿arr當數組首地址用，我們直接引用array類
for(int i = 0; i < 10; i++)
{
cout << arr[i] << endl;
}
cin.get();
return 0;
}
template<class T>
void insertion_sort(T& arr, int count)
{
int p = 0;
for(int i = 1; i < count; i++)
{
auto number = arr[i];
for(p = i; p > 0 && number < arr[p-1]; p--)
{
arr[p] = arr[p-1];
}
arr[p] = number;
}
} </pre>