背景
接上面一篇文章 算法踩坑-快速排序 来继续聊聊最近我写的一些算法的小例程。
主要从以下几方面来说的：
- 插入排序思想
- 插入排序实现
- 插入排序优化
插入排序思想
插入排序的思想是从第i个位置开始，逐个的往前面i个有序的序列中插入第i个元素，最终i到达末尾的时候，整个序列就都是有序的了。
无序序列指针
从第i+1个位置开始遍历，一直到整个序列的末尾N
有序序列指针
从有序序列的前一个位置开始一直往前遍历，一直到序列的开头，把无序序列的元素插入到指定的位置
插入排序实现
插入排序的思想很简单，所以实现也是很简单的，只有不到十行代码
void Insertionsort(ElementType arr[], int count) {
int i;
int j;
for (i = 1; i < count; i++) {
ElementType tmp = arr[i];
// 把i位置的元素插入到前i个元素中
// tmp < arr[j-1] 这个判断条件需要加在for循环的判断条件中，
// 否则会出现j多减1的情况，导致排序出问题
for (j = i; j > 0 && tmp < arr[j-1]; j--) {
// 往后移动一个位置
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}
插入排序优化
从无序的序列中把元素插入到有序序列中，这是插入排序可以优化的部分。
第一种实现方式是：循环交换两个元素
void Insertionsort1(ElementType arr[], int count) {
int i;
int j;
for (i = 1; i < count; i++) {
ElementType tmp = arr[i];
for (j = i; j > 0 && tmp < arr[j-1]; j--) {
// 交换元素
tmp = arr[j];
arr[j] = arr[j-1];
arr[j - 1] = tmp;
}
}
}
这种方式不好的地方在于频繁的交换元素需要付出额外的时间代价
第二种实现：从后往前循环的比较有序与当前的的插入元素，把不符合有序元素逐个的往后移动，直到复合条件位置，这个位置就是插入元素的位置。
ElementType tmp = arr[i];
// 把i位置的元素插入到前i个元素中
// tmp < arr[j-1] 这个判断条件需要加在for循环的判断条件中，
// 否则会出现j多减1的情况，导致排序出问题
for (j = i; j > 0 && tmp < arr[j-1]; j--) {
// 往后移动一个位置
arr[j] = arr[j-1];
}
arr[j] = tmp;
