算法踩坑2-插入排序

背景

接上面一篇文章 算法踩坑-快速排序 来继续聊聊最近我写的一些算法的小例程。
主要从以下几方面来说的：

• 插入排序思想
• 插入排序实现
• 插入排序优化

插入排序思想

插入排序的思想是从第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;

One More Thing

噢！我是算法，点我