（二）直接插入排序法

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;
    }
}