插入排序
1、插入排序--以抓扑克开始逐层通俗讲解
在玩扑克牌时，你的左手拿着已经排好序的牌（有序区），右手不断从牌堆摸新牌（无序区），每一次摸新牌，就在左手的手牌里从右往左比对，把新牌插到合适的位置，全程左牌永远保持有序。
这就是直接插入排序的本质
2、以扑克牌的全过程模拟实现插入排序
设定：
初始牌堆（乱序）：【5，2，4，6，1，3】
左手一开始就只拿第一张牌，天然有序。
第一层：初始状态
左手（有序）：【5】
牌堆（无序）：【2，4，6，1，3】
第二层：摸第二张新牌【2】
1.右手摸牌【2】
2.和左手的【5】作比较，【2】<【5】，把【5】往后挪动一位腾出位置
3.左边没牌了，直接将【2】插入到最左边
4.现在左手有序【2，5】
第三层：摸第三张新牌【4】
1.右手摸牌【4】
2.和左手的【2，5】作比较，【4】<【5】，把【5】往后挪动以为腾出位置，让后再和【2】作比较，【2】<【4】，不用挪动位置，左边没牌了，把【4】插入到刚刚腾出的位置，也就是【2】和【5】的中间位置。
3.现在左手有序【2，4，5】
第四层：摸第四张新牌【6】
1.右手摸牌【6】
2.和左手的【2，4，5】作比较，【6】>【5】，【5】不动，直接将【6】插入到最后面
3.现在左手有序【2，4，5，6】
第五层：摸第五张新牌【1】
1.右手摸牌【1】
2.和左手的【2，4，5，6】作比较，【1】<【6】，将【6】往后挪动一个位置腾出位置，接着比较【5】，【1】<【5】，【5】接着往后挪动一个位置，腾出本身的位置，接着往前【1】<【4】，【4】接着往后挪动一个位置腾出本身的位置，再往前比较【1】<【2】，【2】接着往后挪动一个位置腾出位置，此时左边已经没有牌了，将【1】插入到最左边
3.左手有序【1，2，4，5，6】
第六层：摸最后一张牌【3】
1.右手摸牌【3】
2.和左手的牌进行比较，其中我们省略一点步骤，其中【3】比【4，5，6】都小，都往后挪动一个位置，接着再和【2】比较，【3】>【2】，不动，直接将【2】插入到【2】和【4】中间
3.最后左手有序【1，2，3，4，5，6】
3、对应代码逻辑
1.左手=有序区间，牌堆=无序区间
2.每次取无序区间第一张牌=待插入元素
3.从有序区的最后一个元素往前挨个比较
4.比我大的全部往后移动腾出位置
5.比我小的就直接插入到当前牌的后面，完成插入
4、插入排序的动图展示
5、插入排序的代码实现
上述的代码就是我们在扑克牌当中的代码实现，肯定会有人有一个疑惑，为啥跳出循环之后插入的位置是a[end+1]呢？是因为我们在挪动元素之后我们写了end--这个步骤，让后再进行新的一轮循环，如果这一轮循环比前面的元素大，就跳出循环，那么此时元素就插入到了end+1这个位置。
接着，我们比较了其中的元素，我们继续比较剩下的元素
我们只需要再镶嵌一个循环条件就可以了，这里我们来解答一下外层循环的条件，其中的i<n-1，n代表的元素的个数，我们需要进行比较的次数是n-1次，对应的下标就是[0，n-2]，所以i<n-1
运行代码
希尔排序
希尔排序的基础就是插入排序，其中插入排序的缺点是如果牌很乱，小的数全在后面，要一步一步的往前挪，挪动的次数比较多，很慢。
1.希尔排序的改良思路
（1）先进行预排序（2）在进行插入排序
1、希尔排序的思路
1、先按照固定的间隔进行分组
2、每一组进行插入排序，让大的数尽量往后面，小的数往前面放
3、不断的进行缩小间隔，直到间隔缩小到1，就是普通的插入排序
4、前面进行预排序之后，就会让大的数尽量的都在后面，小的数都在前面，当间隔为1时，直接进行一次插入排序，速度很快
2.以扑克牌为例分析希尔排序
假如手中有待排序的卡片【9，1，2，5，7，4，8，6，3，5】
规则：
根据间隔进行分组，根据c语言的基本规律，我们刚开始一般以3为间隔进行分组
此时我们以间隔3开始分组，也就是gap=3
第一组：【9，5，8，5】
第二组：【1，7，6】
第三组：【2，4，3】
每次一组一组的进行排序，我们先进行第一组排序，首先我们把第一个元素【9】看作天然有序元素，下标是end,让后接着让第二个元素a【end+gap】和a【end】进行比较，如果待插入元素小于当前元素，就让当前元素往后挪动一位腾出位置，但需要注意的是，它的挪动的间隔是3，具体的步骤跟上面我们讲述的直接插入排序步骤一样，只是这里的挪动步骤是3，下面我们以代码的形式写一下第一组的排序
3.插入排序和希尔排序的对比
插入排序
希尔排序
当希尔排序分成一组一组进行排序的时候，希尔排序的其中一组跟直接插入排序的唯一区别就是间隔，直接插入排序的间隔是1，而希尔排序的间隔是3，所以在代码中将1换成了gap=3，其他没什么区别。
4.将多组元素分别进行排序
在上面当中我们进行了第一组的排序，下面我们继续进行第二组，第三组的排序，
此时，我们在外面再嵌套一个循环，我来解读一下为啥是j<gap，因为我们再进行完第一组的排序之后，需要将第二组的第一个元素看作天然有序元素，它的下标在整体的下标是a[1],当第二组的元素进行完排序之后，又该对第三组的元素进行排序，此时第三组的第一个元素对应整体元素的下表是a[2]，所以对应每一组的第一个元素的下标满足j<gap
5.预排序之后，再进行一次插入排序
我们肯定会以为最后的直接插入排序就是简单的将我们开头的直接插入排序粘贴在最后一个位置就可以了，实则不然，如果我们将直接插入直接写在最后，那么前面我们写的不就是多次一举了吗？
这里我们的做法是根据gap进行，刚开始gap=3，顺序还是比较粗糙的，接着我们在进行分组，分成2组，直到最后分成1组，也就是希尔排序的最后一步，就直接达成了最后一步的操作
结果和上面的直接插入排序的结果一样
6.插入排序与希尔排序的效率时间比较
插入排序：假如有10个元素，当我们进行排序时插入排序时最好的选择，而此时我们选择希尔排序就是多此一举，插入排序适合元素个数较少的最佳选择
希尔排序：希尔排序适合元素个数较多的最佳使用，它可以让这些元素当中最大的元素进行跳跃式的往后挪动，让最小的元素最快的挪动到最前面去，效率和时间都比较块，而此时的插入排序就不适用了，因为它需要将大的元素一个一个往后挪动，小的元素一个一个的往前挪动。
本次我们完成了插入排序和希尔排序的编写与效率的对比，两种算法各有各自的使用场景，希尔排序整体性更优。
