【C++笔记】-- 七种排序流食般讲解

1.排序的概念所谓的排序就是对于一组记录按照某个或者某些关键字递增或递减的排序这些记录。2.排序的分类此文章将会介绍四类排序。一、插入排序直接插入排序、希尔排序。二、选择排序选择排序、堆排序。三、交换排序冒泡排序、快速排序。四、归并排序归并排序。3.排序稳定性概念介绍一组的记录当中肯定是会出现相同数值的情况在一开始的时候虽然数值相同但是这些相同数值的数据是有顺序的看一个排序算法是否具有稳定性看的就是在排序之后这些数值相同的数据的顺序有没有变化顺序有变化就说明这个排序算法不具有稳定性顺序没有变化就说明该排序算法具有稳定性。4.七个排序的详情介绍1.直接插入排序升序版在生活当中我们在打牌时对于牌的有序整理就是直接插入排序的具体体现。思路详解有一组数据在数组当中存储我们默认第一个数为有序的然后从他后面的数开始先用一个变量把数据值保存把这个数值在数组中对应的位置空出来我们需要拿着这个数值和他前面的值一次进行比较比较会出现两种情况一、比前面的值小前面的值要往后挪动到空位又有新的空位更新一下空位以及继续要比较的前一个数二、比前一个值大就把变量存的值放进此时的空位里。代码实现。直接插入排序的时间复杂度虽然是On^2有点高但是他是具有实践意义的因为在库里的快排的小区间优化采用的就是直接插入排序。直接插入排序的稳定性稳定的因为他是一一向前比较的在不满足条件的时候直接放在使他不满足条件的数值的后面。2.希尔排序希尔排序其实是直接插入排序的优化版本他是很快的优化完可以跟快排、堆排坐一个桌子了。怎么个优化方式呢通俗来说就是先进行对数据的预处理预处理完事之后再来一次直接插入排序完成排序因为在预处理完事之后待排序的数据是很接近有序的而直接插入排序在对于接近有序的数据时效率是很可观的。之前预处理其实也是用的直接插入排序但是预处理时待排序的数据间隔至少是为一的不然数据就是紧挨着的那么跟进行一次普通的直接插入排序就没有区别了预处理就起不到优化的作用了。预处理采用对一组一组间隔相等的数据排序如果间隔大那么在前面的大数值的数据就能够很快速的跳到后面而后面的小数值的数据也能够快速跳到前面间隔小只是数据跳的速度慢了一点不过同样是具有优化作用的。代码实现有两种写法一是把间隔不同的当作一组这样的一组一组来预处理二就是每组并排走因为间隔不同的一组的小组的排头是一次顺序又循环的。一、二、。间隔gap:其实间隔gap的取法有多种我们代码实现当中采用的是一种相对权威的一种。希尔排序的稳定性不稳定因为在预处理时会分为多组间隔不同的待排序的记录而数值相同的数据显然不会被全部分到一组间隔相同的一组记录当中。3.选择排序思路详解在一个待排序的数组当中会把数组分成两边一边是已经排好的有序区间另一边是待排序区间我们要从待排序区间里面选择最大或者是最小的数据把选出的数据放进有序区间内。代码实现是优化版本的选择排序在同一待排序区间内选出最大值以及最小值两头齐开代码实现注意图中标红。选择排序的稳定性不稳定最大值、最小值的取到相同数值的数据会交换到有序区间里面数值相同的数据的顺序可能会变。4.堆排序思路详解堆排序是利用数据结构堆的特性和其中两个重要的算法为地基的一个排序算法向上调整算法and向下调整算法。要想让数据从大到小排序那么就要建立小堆想让数据从小到大排序则需要建立大堆因为在这个算法里对于数组区间的划分是左边是待拿出来排序的堆数据右边是排好的有序区间拿出堆顶元素放在有序区间、从右往左填数堆的大小也在同步收缩。然后运用向上调整算法建堆或者是运用向下调整算法建堆从第一个非叶子节点开始执行。运用堆的特性取出堆顶元素然后把他交换到数组的最后一个位置堆的最后一个叶子节点然后在这个叶子节点之前的数据都是还没有排序的把他们用向下调整算法调整成堆然后继续之前的操作。这一整个操作都是在顺序存储的数组上直接进行的所以排完序之后数组就是有序的了。代码实现~堆排序的稳定性不稳定因为堆排序对于数据的处理其实是有两步的一步是把数据全部放进堆数据结构里面二是要拿堆顶元素出来放到有序区间里面这两步会影响到同值数据的顺序。5.冒泡排序冒泡排序客观来说是没有实践意义的但是有教学意义。思路详解冒泡的核心是交换如果既定是升序小到大把待排序数据的区间比作一个湖左边就是湖底右边就是湖面冒泡排序的每一趟把此时数据中最大的数据通过两两比较再交换的方式送其至湖面。代码实现~冒泡排序的稳定性稳定的一趟一趟两两交换只交换想要的。6.快速排序快速排序的内容比较多简述一下此次文章涵盖的内容递归和非递归单趟排序的三种版本hoare版本、挖坑法、前后指针法两种优化方式三数取中法选key、小区间优化。找工作时优化方式口述就行。接下来介绍一下递归hoare的组合思路详解单趟的hoare版本是默认最左边的数为key右指针先走找他想要找的值找到后停下让左指针走找左指针想要找的值找到后进行交换此为一次后面都是循环此次直到相遇右指针找到想找的值停下左指针是因为遇到右指针才停下的使用左右指针向中间靠拢左边找比key大的右边找比key小的排个升序一定一定是右指针先走最左边为key右指针就得先走才能保证左右指针相遇的格子的值比key小好跟key位置的值做交换如果选择最右边为key左指针一定先走才能保证左右指针相遇的格子的值比key大好跟key位置的值做交换。递归就是不断把区间缩小单趟结束之后总可以把区间划分成 [left, key - 1] key [key 1, right] 默认key位置是排好序了然后两边区间像第一次的情况处理先单趟再划分区间递归宏观角度再次调用函数相信这个函数能自己完成直到区间不能再缩此时就是递归出口。代码实现递归hoare的组合。再来介绍一下递归前后指针组合思路详解借助前后指针一开始前指针指向key后指针指向key1位置后指针指到的如果是小于key的值前后指针都需要后指针指到的是大于key的值后指针知道后指针越界此时结束单趟。递归都是一样的只是单趟不同。代码实现。挖坑法不做代码实现讲一下思路同样是左右双指针先将第一个数值存进变量key里面让该位置格子可以填值一个指针指向这里另一个指针用来找可以填的值找到后把值填到坑里填完之后刚刚找到值的位置就形成新的坑位了那么另一个指针就要找可填值了如此循环直到两指针相遇把变量值填入这几乎和hoare版本的单趟是一样的一个采用临时变量一个没有罢了。到这我们来介绍一下两种优化方式首先介绍一下三数取中法选key由于一些极端情况会导致选这个key值会让时间复杂度较高我们就可以通过三数取中选取较为均衡的值来当key值避免极端key值带来的麻烦我们是在最左边的值、最右边的值、中间值这三个值中选取大小在中间的值。三数取中代码实现我们再来介绍一下小区间优化由于我们上述的快排是用递归实现的这就会有递归太深栈溢出的风险所以我们就可以在递归区间较小的时候不再继续调用快排函数反而使用其他排序直接进行对区间的排序工作这时候直接插入排序的实践意义就体现出来了库里面的快排小区间优化用的就是直接插入排序。小区间优化代码实现。最后我们来讲一下非递归的形式是怎么实现的因为笔试可能考有必要总结归纳一下快排的非递归的实现是借助栈来模拟实现的函数栈帧的每一次调用跟新的都是区间只有区间有变化所以栈数据结构里面维护的数据就是区间栈的先进后出能很好的模拟递归栈帧的创建、返回等等。非递归的代码实现。快速排序的稳定性不稳定在对区间排序时会对数据进行交换远距离交换不在乎同值数据的顺序的。 其实还有一个实现方式参考荷兰国旗问题在这就不多赘述了。7.归并排序递归形式思路详解归并排序和快速排序一样都是划分区间对区间进行整理但是归并排序有点略微不同他是先把区间划分到最小情况然后在递归返回的时候进行对两个区间为一组的合并排序。递归形式的代码实现。非递归形式的思路详解归并排序的非递归的模拟实现就借助不了栈模拟了因为麻烦对于归并排序的非递归的模拟实现我们会采用循环的方式来实现我们定义一个变量gap来表示向上合并时数据的个数对于同一个gap我们采用循环的方式来两两向上合并这是模拟递归的一层gap模拟的其实是递归层数深度然后处理一下最后合并的边界因为不可能总是数据数相同、偶数对偶数的合并也可能是假设最后两个区间分别为q1 : [l1, r1]、q2 : [l2, r2]第一种情况r2越界第二种情况l2、r2越界第三种情况r1、l2、r2越界。处理完这三种越界情况非递归归并排序就通用了处理这三种情况时也能很好体现在每次合并就把区间拷贝回原数组的好处了省事特判剪枝掉就行。代码实现、。归并排序的稳定性稳定不存在在排序时对数据进行远距离交换。