算法描述：
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
插入排序的c++代码：
template<typename T>
void insertionSort(T arr[], int n)
{
for (int i = 1; i < n; i++)
{
for (int j = i; j > 0; j--)
{
if (arr[j] < arr[j - 1])
{
swap(arr[j], arr[j - 1]);
}
else
break;
}
}
}
接下来比较selectionSort和insertionSort的性能。由于对同一数组进行排序才有可比性，因此需要对随机生成的数组复制一份，然后提供给两个排序算法。在SortTestHelper（）中添加一个拷贝数组的函数copyArray（）
//此处也可考虑用函数模板，只不过涉及到深拷贝的知识，简单起见用了int型
int *copyArray(int a[], int n)
{
int *arr = new int[n];
//copy（）函数包含在std中，a原数组的头指针，a+n原数组的尾指针，arr目的数组的头指针
copy(a, a + n, arr);
return arr;
}
测试代码如下：
#include "SortTestHelper.h"
#include "selectionSort.h"
#include "insertionSort.h"
#include <iostream>
using namespace std;
int main()
{
int n = 10000;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
int *arr2 = SortTestHelper::copyArray(arr, n);
SortTestHelper::testSort("selectionSort:", selectionSort, arr, n);
SortTestHelper::testSort("insertionSort:", insertionSort, arr2, n);
delete[] arr;
delete[] arr2;
system("pause");
return 0;
}
结果：
selectionSort:0.153s
insertionSort:2.8s
理论上分析，插入排序应该比选择排序要快，而上述测试用例表明选择排序更快。为什么会有这种结果呢？
事实上，对于插入排序，在遍历的同时也在不断的进行交换操作，而交换操作比赋值操作更耗时，因为每一次交换操作的背后都有三次赋值操作。
接下来对插入排序算法做些改进。代码如下：
template<typename T>
void insertionSort(T arr[], int n)
{
for (int i = 1; i < n; i++)
{
//寻找arr[i]合适的插入位置
//将arr[i]赋值一份e，用e和其前面的元素进行比较，找到应该插入的位置j后再将e赋值给arr[j]
T e = arr[i];
int j;//保存元素e应该插入的位置
for (j = i; j > 0; j--)
{
if (e < arr[j - 1])
{
arr[j]=arr[j-1];
}
else
break;
}
arr[j] = e;
}
}
测试后结果如下：
selectionSort:0.155s
insertionSort:0.084s
为了进一步说明改进算法的性能，在SortTestHelper（）中定义一个生成近乎有序的随机数的函数，GenerateNearlyOrderedArray（）
//近乎有序数组可看成是从有序数组中随机挑选几组数进行交换之后得到的数组
int *generateNearlyOrderedArray(int n,int swapTimes)
{
//开辟空间后，先生成有序数组
int *arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = i;
}
srand(time(NULL));
for (int i = 0; i < swapTimes; i++)
{
int posx = rand() % n;
int posy = rand() % n;
swap(arr[posx],arr[posy]);
}
return arr;
}
用近乎有序的数组来测试改进后的插入排序算法，其结果为：
selectionSort:0.161s
insertionSort:0.012s
