插入排序——重温排序（一）

在这个系列，我会逐一介绍几种常见的排序。介绍的内容包括：排序的思想、复杂度分析、代码实现等。首先来了解一下插入排序。

前言

有句话说，只有能把学过的东西用自己的话讲给别人听，才能算是真正掌握了。我对此深以为然，于是下定决心开始写技术博客，提升自身技术水平。至于选择写排序的原因有三个：第一个是刚开始写东西，想选比较简单的东西来锻炼一下表达能力，为后续的写作打下基础；第二个是虽说排序比较简单，但是在面试中还是挺多被问到（我就曾经在面试生涯中被问过两次快速排序），可在实际工作中却并不怎么常用，因此时间一久难免生疏，所以刚好也做一下复习；第三个是把知识点重新整理之后，会更方便自己后续的回顾。

一、排序概述

首先简单介绍一下一些排序中的基本概念。

1. 分类

内部排序：整个排序过程都在内存中进行的排序。
外部排序：由于数据量过多，不可能将所有数据都读入内存，因此需要借助磁盘等存储媒介来进行的排序。

2. 基本操作

排序的两个基本操作：比较、移动。

3. 时间复杂度

时间复杂度的衡量标准：比较次数、移动次数。

4. 稳定性

稳定性判断标准：两个相等的元素，排序前后在序列中的顺序是否一致。

二、插入排序

下面步入正题，开始介绍插入排序。插入排序的思想用一句话来描述就是，每一步将一个待排序的元素，按照其关键字的大小，插入到前面已经排好序的有序表的正确位置，直到所有元素插入结束为止。

1. 算法描述

插入排序的算法可以归结为下面3句话。

• 当插入第i(i>=1)个元素时，前面的r[1]、r[2]、...、r[i-1]已经排好序。
• 用r[i]的关键字与r[i-1]、r[i-2]的关键字顺序进行比较，如果小于，则将r[x]向后移动，否则说明已经找到插入位置。
• 找到插入位置即将r[i]插入。

2. 简单图示

这是一个完整的插入排序例子，其中有两个关键字为25的元素，注意观察它们在排序前后的位置关系。

3. 算法实现

下面是简单的C语言实现版本。

void insertSort(int list[], int count) {
    int temp, i, j;
    for (i = 1; i < count; ++i) {
        temp = list[i];
        for (j = i - 1; j >= 0; --j) {
            if (list[j] <= temp) {
                break;
            }
            list[j+1] = list[j];
        }
        list[j+1] = temp;
    }
}

4. 算法分析

从上面的例子可以看出，如果排序前数组已经有序，则每次只需要与有序序列的最后一个元素比较，总比较次数为n-1，不需要移动。
而最坏的情况，每一趟每个关键字每次比较都需要移动，总的比较次数和移动次数都约为 n^2 / 2。
在平均情况下，比较次数和移动次数都约为 n^2 / 4，因此插入排序的时间复杂度是O(n^2)。

从上面图示的例子可以看到，带*的关键字为25的元素，排序前后都在另一个关键字为25的元素后面，因此插入排序是一种稳定的排序。

5. 总结

• 插入排序的时间复杂度为O(n^2)。
• 插入排序是一种稳定的排序。

从插入排序可以看出，当待排序列为正序时，时间复杂度为O(n)，当基本有序的时候，排序的效率也会快很多。
所以有没有一种方法，可以先让序列先变得基本有序，然后再进行插入排序，以此来提高效率呢？

答案是肯定的，那正是下节要介绍的内容 —— 希尔排序。