C++插入排序优化怎么写？

Question

写挂了，有无大 佬帮忙写一下优化？
我写优化总是写出RE……蒟蒻一枚

Answer 1

#include <iostream>
#include <algorithm>
#include "Student.h"
#include "SortTestHelper.h"

using namespace std;

template <typename T>
void insertionSort(T arr[], int n) {
    for (int i = 1; i < n; i++) {
        // 寻找元素arr[i]合适的插入位置
        T e = arr[i];
        int j; // j保存元素e应该插入的位置
        for (int j = i; j > 0 && arr[j - 1] > e; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

template <typename T>
void selectionSort(T arr[], int n){
    for(int i=0; i<n;i++){
        int minIndex = i;
        for(int j=i+1;j<n;j++)
            if(arr[j]<arr[minIndex])
                minIndex = j;
    swap(arr[i], arr[minIndex]);
    }
}

int main() {
    int N = 10000;
    int *arr1 = SortTestHelper::generateRandomArray(N,0,N);
    int *arr2 = SortTestHelper::copyIntArray(arr1, N);

    int swapTimes = 100;
    arr1 = SortTestHelper::generateNearlyOrderedArray(N,swapTimes);
    arr2 = SortTestHelper::copyIntArray(arr1, N);

    SortTestHelper::testSort("Selection Sort", selectionSort,arr1, N);
    SortTestHelper::testSort("Insertion Sort",insertionSort,arr2,N);
    delete[] arr1;
    delete[] arr2;
    return 0;
}