插入排序--2路插入排序

2路插入排序是在折半插入排序基础上进行改进，其目的是减少排序过程中的移动记录的次数，但为此需要增加n和记录的辅助存储空间。

理解：所谓的2-路，是指优先插入在序列前面或后面，然后再考虑插入到中间

通过巧妙的取余运算，找到正确的插入位置。要想理解算法，一定要将数值代入到程序中，用脑子来运算这段代码。只能说这个取余运算很巧妙。

template
void path2insert_sort(vector& array,const int length)
{
vector temp(length);
temp[0] = array[0];//temp中的第一个记录为array中排好序的记录
int first = 0,final = 0;//first用来指示temp中排好序的最小元素，final只是最大元素

for (int i = 1;i {
if (array[i] {
first = (first - 1 + length) % length;
temp[first] = array[i];
}
else if (array[i] > temp[final])//待插入元素比最大元素大，插入到最后面
{
final++;
temp[final] = array[i];
}
else//待插入元素比最小的大、比最大的小，通过遍历以排序的元素查找出入的位置
{
int k = final + 1;
while(temp[k - 1] > array[i])
{
temp[k] = temp[k - 1];
k--;
}
temp[k + 1] = array[i];
}
}
//将排序后的记录复制到原来的顺序表
for (int k = 0;k {
array[k] = temp[(first + length + k) % length];
}
}