void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) {
// 寻找元素arr[i]合适的插入位置
for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
swap(arr[j], arr[j - 1]);
}
}
}
template<typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) { // 从1开始，第0个元素不用考虑，因为它本身就有序了
// 寻找元素arr[i]合适的插入位置
T e = arr[i];
int j; // j保存元素e应该插入的位置
for (int j = i; j > 0 && arr[j-1] > e; j--) { // j从i递减到1，如果arr[j-1]大于e，则arr[j]的值变为arr[j-1](j位置的元素与前一个元素比较，如果大于它则交换位置，最多考察到j>0即j=1的情况)
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
