背景
接上面一篇文章 来继续聊聊最近我写的一些算法的小例程。
主要从以下几方面来说的：- 插入排序思想
- 插入排序实现
- 插入排序优化
插入排序思想
插入排序的思想是从第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;