template<typename T>
void InsertionSortNew(T arr[], int n)
{
    // 默认第一个元素为有序，故从1开始遍历
    for(int i=1; i<n; i++)
    {
        T temp = arr[i];
        // 如果当前的第一个比它之前的元素小，则要移动
        if(temp < arr[i-1])
        {
            int j;
            // 寻找插入的位置
            for(j = i; j > 0; j--)
            {
                if(temp < arr[j])
                {
                    arr[j] = arr[j-1];
                }
            }
            arr[j] = temp;
        }
    }

    return ;
}

把if写在for循环的条件里就对了：

template<typename T>
void InsertionSortNew(T arr[], int n)
{
    // 默认第一个元素为有序，故从1开始遍历
    for(int i=1; i<n; i++)
    {
        T temp = arr[i];
        // 如果当前的第一个比它之前的元素小，则要移动
        if(temp < arr[i-1])
        {
            int j;
            // 寻找插入的位置
            for(j = i; j > 0 && arr[j-1] > temp; j--)
            {
                arr[j] = arr[j-1];
            }
            arr[j] = temp;
        }
    }

    return ;
}