和面试官聊聊「插入排序」的正确姿势

转自景禹

大家好呀，我是景禹。

今日分享一下插入排序，希望你从中有所收获！

面试官最爱考察的是一个被试者对知识掌握的灵活程度和熟练程度，当一道题目可以同时考察到被试者多个知识点的掌握程度和思考能力时，面试官最爱这样的题目，而且对于插入排序这样被大家耳熟能详的知识点，常常成为考点。

插入排序

插入排序简单的就像你玩扑克牌（双Q，斗地主）。基本操作就是将一个记录插入到已排好序的有序表中，直到将所有的未排序记录插入到适当的位置。

插入排序好简单

将其插入正确洞

直到插完所有洞

为了深入理解插入排序，来看一个简单的例子。

刚开始，我们将数组的第一个元素 5 当做有序元素，假设他在正确的 “洞”：

然后将 1 插入到正确的洞，将 1 与 5 比，1<5 ，5 前面再没有任何元素，所以 1 正确的洞就在 5 的前面：

将 4 插入到正确的洞，将 4  和 5 比较， 4 < 5；将 4 和 1 比较，4 > 1 ，所以 4 正确的洞就在 1 和 5 之间，将 4 插入 1 和 5 之间：

将 2 插入到正确的洞，将 2 与 5 比较，2 < 5；将 2 与 4 比较，2 < 4；将 2 与 1 比较，2 > 1，所以 2 正确的洞应该在 1 和 4 之间：

将 8 插入到正确的洞，将 8 和 5 比较， 8 > 5  ，所以 8 的正确的洞就在当前位置：

然后将最后一个记录 4 插入到正确的洞，将 4 和 8 比较，4 < 8；将 4  和 5 比较，4 < 5；将 4（当前记录） 与 4（已排序） 比较，两者相等，所以当前记录 4 正确的洞在已排序的 4 和 5 之间：

再来看实现代码就再简单不过了

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++) { 
        key = arr[i]; //当前要插入正确洞的记录
        j = i - 1;  // 将 key 插入正确的洞
        // 在 0 到 i-1 中找到 key 的正确洞
        while (j >= 0 &&  key < arr[j]) { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = key; 
    } 
} 

for 循环从 i = 1 开始，是因为 i = 0 的元素我们当做有序元素处理，while 循环做的事情就是将当前记录 key  插入正确的洞。

复杂度分析

时间复杂度分析

内层 while 循环的次数取决于待插入记录的关键字 key 与前 i -1 个记录的关键字之间的关系。

当 i = 1 时，while 循环中最差情况与 arr[0] 比较一次，并将记录 arr[0] 后移。

当 i = 2 时，while 循环中最差情况与 arr[0] 和 arr[1] 各比较一次，并将记录 arr[0] 和 arr[1] 后移。

……

当 i = n – 1 时，while 循环中最差情况与 arr[0] 到 arr[n-2] 的元素都要比较，并将记录后移。

∴ 最差情况下比较和移动次数为 1 + 2 + … + (n – 2) + (n – 1) = n(n – 1) / 2 .

∴ 最坏的时间复杂度为 量级。

最好情况下，while 循环每一次都仅执行一次，总的执行次数就是外层 for 循环的次数，最好的时间复杂度为 量级。

空间复杂度分析

插入排序的没有使用额外的空间，为原地排序算法，所以空间复杂度为 .

稳定性分析

在之前讲的示例中，我们可以看到排序前后的两个 4 的相对位置没有发生变化：

排序前：

排序后：

插入排序稳定的根本原因是，待插入的元素不会插入到与自身值相同的关键字之前，所以排序前后值相同的关键字的相对顺序被保留了下来。

实战演练

二分插入排序

从名字就能看出来，运用了二分查找的插入排序。在上面标准的插入排序算法中，我们会将待插入关键字 key = arr[i] ，然后在数组 [0，i - 1]  的范围内查找待插入关键字 key 的正确位置，这里的查找操作的时间复杂度为 量级。但是如果使用二分查找在数组 arr 的 [0,i - 1] 的范围内查找关键字 key ，那么就可以将查找操作的时间复杂度降到 量级。关于二分查找不熟悉的可以看一下这篇文章 二分查找就该这样学 。

这样，就可以将标准的插入排序优化如下，一般最好自己能写出二分查找：

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    int loc;
    for (i = 1; i < n; i++) { 
        key = arr[i]; //当前要插入正确洞的记录
        j = i - 1;  // 将 key 插入正确的洞
        
        // 使用二分查找找到 key 正确的洞
        loc = binarySearch(a, key, 0, j);
        
        while (j >= loc) { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = key; 
    } 
} 

二分查找就不写了奥！不会的看文章。但是这里仅仅只是将查找待插入关键字 key = arr[i] 的正确洞的时间降到了 ，但是需要将 [loc，i-1] 的关键字向后移动，所以二分插入排序的时间复杂度依旧是 。

递归实现插入排序

这道题目能考察到你对于递归和插入排序两个知识点的理解程度。对于递归的三要素，不再强调，我们一起看一下实现代码：

//1.进行插入排序
void insertionSortRecursive(int arr[], int n) 
{ 
    //2递归的出口，仅有一个元素时有序 
    if (n <= 1) 
        return; 
  
    //3.对前 n-1 个元素递归进行插入排序
    insertionSortRecursive( arr, n-1 ); 
  
    // 归：将关键字key插入到正确的位置
    int key = arr[n-1]; 
    int j = n-2; 
  
    /* 将key之前arr[0,i-1]中比 key 大的元素向后移动*/
    while (j >= 0 && arr[j] > key) 
    { 
        arr[j+1] = arr[j]; 
        j--; 
    } 
    arr[j+1] = key; //将key放入正确的洞
} 

我们将数组 arr = [5,1,4,2,8,4] ，n = 6 带入上面的代码：

我想看完这个图，结合插入排序，定对你理解递归有帮助。

交换实现插入排序

标准的插入排序中，需要将 arr[0,i-1] 中大于 arr[i] 的关键字向后移动，这里我们不再采用这种方式，而是在比较之后，如果满足大于的关系，直接交换两个元素。如下面动画中将关键字 2 插入到正确的洞，采用交换实现：

void insertionSort(int arr[],int n) 
{ 
    int i, j; 
  
    for (i = 1; i < n; i++) { 
        j = i; 
        // 将 arr[j] 插入到 arr[0,i-1] 正确的位置
        while (j > 0 and arr[j] < arr[j - 1]) { 
     //交换
            swap(arr[j], arr[j - 1]); 
     j--;
        } 
    } 
} 

代码是不是简洁多了，但是同时也要意识到这里最坏情况下的时间复杂度依旧是 .

有兴趣的可以尝试一下递归的写法，这里给出参考代码，一定要自己动手写了再回来看（至少脑子里过一遍）。

void insertionSortRecursive(int arr[],int n) 
{ 
    if (n <= 1)
        return;
    
    insertionSortRecursive(arr, n-1);
 int j = n-1;
    while (j > 0 and arr[j] < arr[j - 1]) { 
        //交换
        swap(arr[j], arr[j - 1]); 
        j--;
    } 
}