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