插入排序基本原理
每次从【未排序】中选取第一个元素放置到【已排序】的正确位置
版本1：直接开辟n的空间
版本2：直接插入排序，无哨兵
Sort::DirectInsertionSort_2() {
int tmp;
/*从[1]开始，[0]已经有序了*/
for(int i = 1; i < sorted.size(); i++) {
/*反之，[i]的位置本来就是正确的，不需要交换*/
if(sorted[i] < sorted[i-1]) {
tmp = sorted[i];
moveTimes++;
int j = i - 1;
/*每次循环把[i]插入到[0:i-1]的正确位置*/
for(; j >= 0 && tmp < sorted[j]; j--) {
compareTimes++;
sorted[j+1] = sorted[j]; //后移
moveTimes++;
}
compareTimes++;
sorted[j+1] = tmp;
moveTimes++;
}
}
}
