算法导论学习之插入排序
《算法导论》买了好久了，基本上没怎么看，最近思想上有了转变，觉得学习才是王道。准备重新拾起来学习，下面我就《算法导论》中的排序算法中的
插入排序做了个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}; // 1for (int i = 1; i < sizeof(array)/sizeof(int); i++) { // 2int key = array[i]; // 3int j = i-1; // 4while (j >= 0 && array[j] > key) { // 5cout << array[j] << " " << key << endl; // 6array[j+1] = array[j]; // 7j--; // 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个元素的序列需要排序，序列如下图：
如下图中的红色箭头将序列分为左、右两部分：左边只有一个元素是4
红色箭头左边的4相当于是我们左手中的扑克牌，红色箭头右边的相当于是一堆扑克牌，我们每次从这堆扑克牌中翻最上边的一张牌。
左边的序列中只有一个元素4，所以是有顺序的。右边的序列，就像一堆扑克牌一样，扣在下面只有我们翻开起最上边的一张牌时，我们才能看到，这张牌到底是什么，其它牌是什么，我们根本看不到（所以我们后面的元素都打码了）。下面我们抽取右边的第一个元素，插入到左边的序列中。我们首先把右边的第一个元素保存起来，做个备份，要不然一会儿在移动的过程中，会把这个元素给冲掉。如图：
这时候，我们会把2与左边的序列从右向左进行比较，由于2<4，所以把4向右移动一个位置。如图：
所以，明白了，我刚才为什么要把2（右边序列的第一个元素）先做个备份吧，最后我们再把2存放到第1个位置。如图：
现在左边的序列是2,4是有序的，红色指针向右移动一位，黑色指针指向红色指针左边的第一位，下面我们再取右边序列的第一个元素，如下图：
我们首先拿1与左边序列从右向左第一个元素即4进行比较，1<4，把4向右移动，同时，黑色指针向左移动一位，如图：
接下来，再让1与2比较，1<2，把2向右移动一位，黑色指针向左移动一位，如图：
由于，黑色指针已经指向了序列外，在左边的序列中，已经没有比1更小的元素，所以，1应该排在黑色指针右边的位置，如图：
现在，左边的序列已经是有序的，红色指针再向右移动一位，黑色指针指向红色指针左边的第一位。下面取出红色指针指向的元素，如下图：
我们比较红色指针指向的元素，与黑色指针指向的元素，6>4，由于左边的序列是有序的，而且是从小到大排序的，所以左边再没有元素比6大，所以6就应该插入到黑色指针右边的位置（看起来没有变化，相当于是6=6，把6赋值给6），如图：
通过上面的图片演示，估计大家对插入排序有了较清晰的认识。
红色指针相当于是外层循环中的 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
参考资料：
《算法导论》
本是古典 何须时尚
今天药忘吃喽~
小灰灰
Myth丶恋晨
还没有评论，来说两句吧...