算法导论学习之插入排序

今天药忘吃喽~ 2022-08-25 10:53 137阅读 0赞

《算法导论》买了好久了，基本上没怎么看，最近思想上有了转变，觉得学习才是王道。准备重新拾起来学习，下面我就《算法导论》中的排序算法中的

插入排序做了个c++的简单实现，附加解释一下自己对下面的这段代码的理解。

#include "iostream"
    using namespace std;
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	
    	int array[10] = {5,6,1,9,0,3,4,8,2,7};   // 1
    	
    	for (int i = 1; i < sizeof(array)/sizeof(int); i++) { // 2
    		int key = array[i];  // 3
    		int j = i-1;   // 4
    		while (j >= 0 && array[j] > key) {  // 5
    			cout << array[j] << " " << key << endl;  // 6
    			array[j+1] = array[j];  // 7
    			j--; // 8	
    		}
    		array[j+1] = key; // 9
    	}
    
    	return 0;
    
    }

插入排序就好像我们玩儿扑克牌一样，我们左手握着扑克牌，右手一张一张的接牌，左手中的牌总是有顺序的。

比如左手中的牌是：红桃2，红桃5，红桃6，这时右手中揭上来了一张红桃3，我们会整理左手中的牌，把红桃3插入到红桃2与红桃5之间，现在左手中的牌是：红桃2，红桃3，红桃5，红桃6。

这时，右手又揭上来一张红桃4，我们再次调整左手中的牌，把红桃4插入到红桃3与红桃5之间，调整后左手中的扑克牌是：红桃2，红桃3，红桃4，红桃5，红桃6。

插入排序有3个特点：

1、插入元素前，原来的序列是有序的。

2、每次只插入一个元素。

3、插入元素后，原来的序列的长度增加了1，但仍然是有序的。

下面我将图文并茂的展示插入排序（升序排序）的执行过程。

假如，我们有10个元素的序列需要排序，序列如下图：

![20141016215816500][]

如下图中的红色箭头将序列分为左、右两部分：左边只有一个元素是4

![20141018112238768][]

红色箭头左边的4相当于是我们左手中的扑克牌，红色箭头右边的相当于是一堆扑克牌，我们每次从这堆扑克牌中翻最上边的一张牌。

左边的序列中只有一个元素4，所以是有顺序的。右边的序列，就像一堆扑克牌一样，扣在下面只有我们翻开起最上边的一张牌时，我们才能看到，这张牌到底是什么，其它牌是什么，我们根本看不到（所以我们后面的元素都打码了）。下面我们抽取右边的第一个元素，插入到左边的序列中。我们首先把右边的第一个元素保存起来，做个备份，要不然一会儿在移动的过程中，会把这个元素给冲掉。如图：

![20141018112724453][]

这时候，我们会把2与左边的序列从右向左进行比较，由于2<4，所以把4向右移动一个位置。如图：

![20141018112933937][]

所以，明白了，我刚才为什么要把2（右边序列的第一个元素）先做个备份吧，最后我们再把2存放到第1个位置。如图：

![20141018113140625][]

现在左边的序列是2,4是有序的，红色指针向右移动一位，黑色指针指向红色指针左边的第一位，下面我们再取右边序列的第一个元素，如下图：

![20141018120135731][]

我们首先拿1与左边序列从右向左第一个元素即4进行比较，1<4，把4向右移动，同时，黑色指针向左移动一位，如图：

![20141018120430669][]

接下来，再让1与2比较，1<2，把2向右移动一位，黑色指针向左移动一位，如图：

![20141018121048174][]

由于，黑色指针已经指向了序列外，在左边的序列中，已经没有比1更小的元素，所以，1应该排在黑色指针右边的位置，如图：

![20141018121529989][]

现在，左边的序列已经是有序的，红色指针再向右移动一位，黑色指针指向红色指针左边的第一位。下面取出红色指针指向的元素，如下图：

![20141018122114515][]

我们比较红色指针指向的元素，与黑色指针指向的元素，6>4，由于左边的序列是有序的，而且是从小到大排序的，所以左边再没有元素比6大，所以6就应该插入到黑色指针右边的位置（看起来没有变化，相当于是6=6，把6赋值给6），如图：

![20141018122114515][]

通过上面的图片演示，估计大家对插入排序有了较清晰的认识。

红色指针相当于是外层循环中的 i ，黑色指针相当于是内层 while 循环中的 j 。只要控制好外层循环与内层循环，插入排序还是容易写得出来的，不需要死记硬背。

外层循环控制着待插入的元素，内层循环控制，左边有序的序列，一次与待插入的元素进行比较。当左边的元素比待插入的元素大时，左边的元素，挨个向右移动。

代码很简短，主要是由两重循环构成的，外循环主要是控制循环的趟数，如果有n个元素则需要n-1趟外循环

int key = array\[i\];这句是保存待插入的元素，如果不保存的话，后面向右移动元素会把待插入的元素冲掉（array\[j+1\]） = array\[j\];）

int j = i - 1;则是内循环的右边界，在\[0,j\]这个区间内与key进行比较，在\[0-j\]区间内的元素是从小到大有序的。

如果待插入的元素key小于array\[j\]，那么array\[j\]应该向右移动，即array\[j+1\] = array\[j\]，然后待插入的元素key依次再与array\[j\]左边的元素做比较，

所以有j--；

内层循环结束后表示key<array\[j\]且key>=array\[j-1\]，所以key应该插入在j的位置上，由于在内层循环while中有了j--;所以循环结束后key的插入位置为j+1即array\[j+1\] = key；

参考资料：

《算法导论》

[20141016215816500]: /images/20220824/c2729d0892fc44a6bcc490425c082aaa.png
[20141018112238768]: /images/20220824/8264b48565374a47bb6eb5c1a094bdaa.png
[20141018112724453]: /images/20220824/e72f9e9e56f942ff85b8dee151033fcf.png
[20141018112933937]: /images/20220824/8ee7427e9f0145b981c228a129b8a7f1.png
[20141018113140625]: /images/20220824/a95a53e7ee4f49868193e58421d37254.png
[20141018120135731]: /images/20220824/b1930371dcc34cfc8fcdd7a0133c1e7d.png
[20141018120430669]: /images/20220824/7a24401137cb4d789c0d314299c731c6.png
[20141018121048174]: /images/20220824/57cf9064a58e44f2afa2b53ba962a5f4.png
[20141018121529989]: /images/20220824/f42f3b631ec04c518ad977102001b1a6.png
[20141018122114515]: /images/20220824/4e391f53693a47eabf28cc4599efe383.png