大家好！
数据结构与算法这一讲继续第八章内排序的学习。
今天我们介绍插入排序以及它的变种-Shell排序。
插入排序的这么一个思想呢， 我们可以用 在打扑克牌的时候理牌来进行一个形象的说明。
如果我们这些扑克牌已经整理好， 当新牌来的时候呢，我们希望插到相应的这个位置，
我们会是怎么处理呢？
我们来看这个插入排序的这么一个示例。
对于只有一个元素的情况， 它已经是有序的 如果是有两个元素呢，我们就比较一下。
如果逆序，它就交换。如果已经有序呢， 我们就可以不处理了
比如说对于这个78， 它跟这个前面子序列相比，它正好应该待在这个位置。
在12来进行排序的时候呢，它就会往前面逐个的比， 找到它的合适的位置给待着。
我们对其他的元素呢，也是采用刚才的处理方法。 每个元素在前面的一个已排序子序列里面
找到自己合适的位置，待在那
最后所有的元素都处理完，我们就完成了整个排序的过程。
我们看一下插入排序的算法框架。
首先呢，我们把这个待排序的这个元素， 我们把它找出来，放到一个临时变量里面。
然后呢，我们在它这个位置往前呢 一直在前面查找。
我们找到某一个元素的这个位置呢， 它是比我们待排的这个元素呢，
要小，但是呢，它后面的个元素呢， 比我们比我们待排的这个元素呢要大。
这就是我们这个待排元素它所希望待的位置。
找到这个位置以后，我们把这个刚才放在 临时变量里面的这个元素呢，给它放回去
我们这个循环呢，从第一个元素到第N个元素， 一直这么进行
最后呢，我们就处理完了整个这个排序的过程。
我们看一下插入排序它的算法。
首先它是稳定的，因为每一个元素它在插入的时候
它都是在逐个的进行比较，它没有一个大的跨度。
空间呢，它只用到了一个 临时的变量来存放待排的这个元素，
所以是theta 1
它的最好的情况下呢，时间代价可以是theta n的
这种情况就是它正好是正序的
我们每次呢，只需要跟前面那一个元素进行比较 就发现，也就是正序，只要n-1次比较。
其实呢，如果我们写法跟我们刚才的算法框架不一样， 它可以是，没有移动的要求，
但是我们刚才的算法呢， 是不管它的元素是个什么情况，我们先把这个待排的放到这个临时变量里面，
找到位置以后呢，又给它腾回来，
所以，即使在最佳情况下，它不需要继续往前比 但是我们已经把它扔出去放到临时变量了
而这个位置呢就是它当前呢自己在的这个位置。 也得要给它赋值回来，所以需要2(n-1)次这样的移动。
最差的情况下，就反过来，是一个逆序的情况。
我们在比较上呢，一直要比到这个最前头的那个元素，才完成。
因此呢，它是一个theta n方的时间代价。
移动次数呢，它也是要 一直移到最前端。
那么再加上我们那两个的辅助移动， 也就是我们先把这个元素放到临时变量里面，
然后找到位置，再给他腾回来 就是这个求和呢就是i+2，从1到n-1来进行。
最后的结果也是theta n方的， 平均情况下的这个代价，还是theta n方的代价。
插入排序，它有两个很好的性质
第一个呢就是在基本有序的情况下 它的时间代价是非常低的，非常有效
我们看到刚才这个正序的情况下，它就是最好的时间代价。
还有对于短序列呢，我们的插入排序也是非常有效的。
Shell排序就应用了这两个性质
我们来看一下Shell排序的思想。
我们首先呢把这个整个待排的序列分成若干个小序列，
在小序列里面呢，进行插入排序，它还是非常有效的。
我们逐步增加这个小序列的规模， 减少小序列的个数，
我们的这个待排的序列的整体情况呢， 逐步地趋于更加有序
最后一轮呢要注意
对所有的元素，我都要放到整个这个待排数组里面 进行一个插入排序的整体的处理。
才能完成排序的这样的一个过程。
我们看一下Shell排序的动画演示。
首先我在这个里面呢，找到两个元素， 它实际上是跨越半个数组，
然后呢，对它进行比较。
接着呢，我们在下一轮，就是说 把这个数组的元素个数呢，我们给它增大一倍，
就是4个元素一组， 还是用插入排序来进行它的处理。
接着，我们在最后一轮呢，
就是把所有的元素都放到这个数组里面 进行一个插入排序的处理。
我们可以看到，最后一轮其实元素的这个比较和交换次数已经不是太多了
因为经过上面几轮的处理，它已经基本有序了，我们整个这个排序过程呢，就完成了。
我们看一下，增量除2递减的这么一个Shell排序框架。
我们的增量呢，最开始设为n/2，也就是说，整个跨越半个数组 来取两个元素为一组
在下一轮循环呢，这个增量呢除2，接着呢，一直除， 除到呢这个增量delta呢，小于等于1为止。
在每一个这个子的序列里面，我们总共是有delta个这样的子序列，
我们进行插入排序，注意我们这里，掺入的参数呢 是这个子序列里面第一个元素的下表的这个 起止的地址。
它的这个，数组里面这个元素的 这个有效的这个，最后这个元素的下标呢，是n-i
其实也就是说，它这个有效元素的这个个数呢，我们除掉了前面那些已经处理过的这些增量的那几个子序列的第一个元素，然后从这开始。
也就是说，我们最后，数组能达到的这个下标位置只是n-i
然后呢这个插入排序它是以delta为这么一个逻辑的步长，
在delta这个步长里面它们才是一组进行这样的一个插入排序的整理。
最后呢要注意，如果你这个序列不能保证最后一次的这个排序呢
使所有的元素都进到这个数组里面来进行插入排序
你一定要加这么一条，就是步长为1的 这么一个对整个数组呢进行插入排序。
在我们这个增量除2递减的这样的一个排序处理里头
我们最后一次可以保证是能够达到一次 delta等于1的这么一个步长，它所有的元素，都进来处理。
我们修改以后的 这样的一个插入排序的框架呢
就是，我们是从这个下标等于delta的这个元素，开始处理，
它前面那个元素呢，就是下标i=0。
然后这个界呢，就是你传进来的这个界。
我们这个数组呢是要以这个delta为步长，来逻辑上组成一个这样的子序列。
在处理 每一个这个待排序的这个子序列的时候呢
我们是从当前这个位置i，往前面看，我们以delta为步长一个个地跳着看，
直到某一个元素呢，它呢，是比我们这个待排的这个i，这个元素， 它要小，
而这个j+1，也就是说，我们找到这个位置的它的这个邻居，这个右邻的这个元素呢，
又比我们这个，待排的这个元素i，它要大
就是i能够放到这个相应的这个中间的这个位置。
好，找到这个位置呢，我们就break出来，如果没找到，我们继续往前找。
而且呢，我们这个待排的这个元素i的这个的数值，已经被我们逐步的 交换到了我们当前这个j下标所在的这个位置
所以我们一直往前头进行，我们，要么呢，就是说直到把它放到数组的最开始那个位置，或者是说在中间某个位置，
我们已经找到它的相应的位置，就停止。
好，我们Shell排序呢，它显然是一个不稳定的排序， 因为我们可以看到， 它的跨度是非常大的。
它在组成这样的一个逻辑的子序列的时候，它可以有很大的这个跳跃。
它的空间代价呢，是theta(1)的
这个主要是用在我们进行这个swap交换的时候， 我们用到了这么一个临时变量。
从时间代价来说，如果我们是每次除2递减，它还是一个theta n方的这么一个代价， 还是相当的低效的。
我们可以适当的修改这个增量序列，使得时间代价呢 越来越好
我们看一下这样的修改。我们来看为什么增量除以2递减它的时间代价是比较低效呢？
其实比较显然的就是我们在选择增量的时候呢，它们没有互质。
例如我们刚才看到这样的45和34‘， 它们在这一轮是在同一个子序列里面，
到了下一轮，它们还在同一个子序列里面，这就是使得它的这个比较运算呢，它是比较低效的
也就是说，原来上一轮，它们比较过，处理过，你现在，还在比较，还在处理，这就是它低效的原因。
为了改进它，我们就是打破这样的一个，不互质的现象。
我们就是打破这样的一个，不互质的现象。 比如说我们刚才呢的序列呢，就是 2的k次方，然后2的k-1次方，这样的增量序列。
也就是说它成倍的这个关系。
如果我们稍微打破一下，我们变成2的k次方减1，2的k-1次方减1，
哎，它就已经不是那样的一个，就是有倍数的关系了，它就有点互质了。
还有呢，我们也可以采用，以增量除3递减的方式
这两种方法就是Shell(3)和我们这边减了1以后的Hibbard增量序列，它们的排序效率都可以达到theta n的1.5次方
我们选取其他的序列还可以得到更好的一个时间代价
例如2的p次方乘以3的q次方这样的形式的序列呢，它可以达到theta n乘以log n的时间代价。
最后我们留给大家几个思考题，
也就是，插入排序呢，如果我们发现逆置对的时候，我们就交换，不是我们最后找的这个位置，再把这个数据腾进去，
还有呢，我们查找相应的位置的时候，我们采用二分法， 而不是像前面逐位的比较。
在Shell排序里面我们特别要考虑下这个增量它的作用是什么，
然后我们仔细研究一下增量为2和增量为3的这个子序列，哪个更好，为什么呢？
还有是，我们Shell排序，每一轮子序列的排序在我们前面是用到了插入排序， 我们是不是可以用其他的方法来替代？
谢谢大家！