Insertion Sort
对于近乎有序的数组，插入排序的时间复杂度优于O(nlogn)
对于完全有序数组，插入排序时间复杂度会降到O(n)
将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入前面有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
和打扑克牌类似，手中的都是排好序的，抽到一张牌后，会插入到已排好序的牌中合适位置
从第二个元素开始，往前比较
算法步骤
template<typenameT>
voidinsertionSort(Tarr[],intn){
//从第二个元素开始插入排序，直到末尾
for(inti=1;i<n;i++){
//从后往前比较，如果大于前面元素，说明是在合适位置，跳出当前循环
for(intj=i;j>0;j--){
if(arr[j]<arr[j-1])
swap(arr[j],arr[j-1]);
else
break;
}
}
}
上述代码虽然可以提前终止内层循环，但是时间性能测试是没有选择排序快的
intmain(){
intn=10000;
//生成乱序数组
int*arr=SortTestHelper::generateRandomArray(n,0,n);
int*arr2=SortTestHelper::copyIntArray(arr,n);//复制arr得到arr2
//测试耗时
SortTestHelper::testSort("selectionSort",selectionSort,arr2,n);
SortTestHelper::testSort("insertionSort",insertionSort,arr,n);
//释放空间
delete[] arr;
delete[] arr2;
return0;
}
/*
selectionSort : 0.16 s
insertionSort : 1.484 s
*/
优化
因为swap函数进行了三次赋值，赋值是比比较操作更加耗时的，可以减少赋值从而进行改进
先将要插入的元素存储起来，再将要插入的元素依次与前面的元素进行比较，小于前面元素的话，就将前面元素赋值到当前位置，直到要插入的元素大于等于前面元素。可以看到通过一次赋值替换了交换操作（三次赋值）
template<typenameT>
voidinsertionSortPlus(Tarr[],intn){
//第一个元素显然有序，因此我们从第二个元素开始排序，若间隔为gap，则从下标为gap开始
for(inti=1;i<n;i++){
//记录要进行排序的元素
Te=arr[i];
//j是要插入的位置
intj;
for(j=i;j-1>=0;j=j-1){
if(e<arr[j-1])
arr[j]=arr[j-1];
<<<<<<<HEAD
elsebreak;//明显当e>=arr[j-1]时跳出循环，说明arr[j]正是元素要插入的位置，而之前arr[j]已经后移一位
=======
elsebreak;//明显当e>arr[j-1]时跳出循环，说明arr[j]正是元素要插入的位置，而之前arr[j]已经后移一位
>>>>>>>27c092bbe831973f875c92f374e0f8ec3ae3e3b4
}
arr[j]=e;
}
}
selectionSort : 0.158 s
insertionSort : 0.113 s
当数据是近乎有序的，插入排序的时间复杂度甚至优于O(nlogn)
// 生成一个近乎有序的数组，n是数组元素个数，swapTimes是指交换次数，因为数组要保持近乎有序
int*generateNearlyOrderedArray(intn,intswapTimes){
int*arr=newint[n];
for(inti=0;i<n;i++)
arr[i]=i;
srand(time(0));
for(inti=0;i<swapTimes;i++){
intposx=rand()%n;
intposy=rand()%n;
swap(arr[posx],arr[posy]);
}
returnarr;
}
intmain(){
intn=10000;
//生成近乎有序数组
int*arr=SortTestHelper::generateNearlyOrderedArray(n,100);
int*arr2=SortTestHelper::copyIntArray(arr,n);
//测试耗时
SortTestHelper::testSort("selectionSort",selectionSort,arr2,n);
SortTestHelper::testSort("insertionSort",insertionSort,arr,n);
//释放空间
delete[] arr;
delete[] arr2;
return0;
}
selectionSort : 0.155 s
insertionSort : 0.003 s
