程序员面试系列——插入排序

短命女 2022-06-11 01:10 157阅读 0赞

插入排序在算法思想中属于“减治法”。

减治法的基本思想是：规模为n的原问题的解与较小规模的子问题的解之间具有某种关系。由于存在这种关系，所以只需求解其中一个较小规模的子问题就可以得到原问题的解。

插入排序就是基于“减治法”中的“减一技术”实现的。如果题目要求对a\[0\]到a\[n-1\]进行排序，我幻想从a\[0\]到a\[n-2\]已经是有序的了，那么我需要做的就是在这些有序的元素中为a\[n-1\]找到一个合适的位置，然后把它插到那里就行。

虽然插入排序基于递归思想，可从顶至下实现；但是，从底至上地实现这个算法——使用迭代会效率更高。从a\[1\]开始，到a\[n-1\]为止，a\[i\]被插入到数组的前i个有序元素中的适当位置上（但是，和选择排序不同，这个位置一般来说并不是它的最终位置）。

示意图如下。

![这里写图片描述][SouthEast]

C语言代码如下。

/* a是整形数组的首地址 * len是数组长度 * 排序结果为非降序 */
    void insert_sort(int *a, int len)
    {
        int i,j,temp;
    
        for(i=1; i<len; ++i)
        {
            if(a[i-1] <= a[i]) //a[i]已经在合适的位置上了
                continue; //处理下一个数
    
            temp = a[i]; //因为移动元素会覆盖a[i],所以把a[i]暂存起来
            j = i-1;
            while((j >= 0) && (a[j] > temp))
            {
                a[j+1] = a[j]; //a[j]向后移动一个位置
                --j;
            }
            a[j+1] = temp; //插入a[i]
        }
    }

【参考资料】  
《算法设计与分析基础（第3版）》（清华大学出版社）第4.1节

[SouthEast]: /images/20220611/eba70958049940618a3281ddf88c46bc.png