1.插入排序插入排序的时间复杂度为O(n^2)最坏的情况是逆序最好的情况是走一趟就有序也就是O(n)插入排序和斗地主相似你会将牌按一定顺序排列下面以升序为例我们先创建一个数组a规定[0end]为有序用temp把a[end1]的值储存起来每次将end1位置的数据插入进来比较a[end1]与a[end]的大小如果a[end] a[end1]就将a[end1] a[end]end--(也就是将数据往后挪)再比较a[end1]与a[end]的大小当a[end]a[end1]时a[end1] temp这是单趟总趟数是用for(int i 0 ; i n-1;i)其中n是数组中的数据个数每次将end i,用temp把a[end1]的值储存起来代码如下这里有两个容易出错的地方一个是for循环中i n-1写错会导致数组越界访问另一个是为什么不在循环里写a[end 1] temp因为有可能数组的第一个数字也要往后挪这样会导致end -1,直接跳出循环不执行a[end 1] temp所以写在循环外。2.冒泡排序冒泡排序的时间复杂度为O(n^2)最坏情况是逆序最好情况是走一趟后flag 0没有发生交换也就是O(n),冒泡排序是两两交换以升序为例代码如下n是数组中的数据个数第一次冒会把最大的放在最后第二次冒会把较大的放在后面依此类推注意写单趟时j n- i- 1,容易出错因为每次都会把大的排好假设n为5第一次冒完后只需再排4个数第二次冒完后只需再排3个数依此类推也就是n- i再减1是因为当i0j4时a[j1]会越界。3.希尔排序通过对插入排序的了解我们知道当数据逆序时它的效率就比较低了这时我们就可以用希尔排序来提升效率通俗来讲希尔排序就是对插入排序的优化它是先对数据进行预排序(让数据接近有序让大的数尽量在后面小的数尽量在前面)最后一趟用插入排序以升序为例:我们将数据分为三组(gap 3)再对这三组数据进行插入排序如图也就是先排蓝色线连接的再排绿色的最后排粉色的。蓝色排完是1,2,5,6绿色排完是3,7,13粉色排完是8,9,10预排序排完是1,3,8,2,7,9,5,13,10,6。预排序代码如下:我注释掉的部分是我上面说的思路一组一组排但是三层循环写得繁琐可以写成两层循环也就是多组同时排蓝色的5,6排完后排绿色的13,3在排粉色的8,9在排蓝色的依此类推。不过这两种写法效率都一样。有人会说gap只能是3吗当然不是那gap为多少才好呢gap越大那么大的数越快到后面小的数越快到前面但越不接近有序反之gap越小大的数越慢到后面小的数越慢到前面但越接近有序当gap1时就是插入排序了。有人说gap是变化的gap gap/31可以保证最后一次gap为1(gap到底是多少没有结论)代码如下:希尔排序的时间复杂度为O(n^1.3)如果要算的话很复杂不过我们可以粗略算一下(gap gap/31忽略掉1gap一开始为n所以gap n/3)有gap组数据每组数据个数为n/gap所以每组3个数据最坏情况(逆序)第一趟排序消耗为(12)*n/3 n(每组比较次数*组数)第二趟排序消耗为(123...8)*n/9 4n不过第二趟是按照最坏情况计算的其实第一趟排完后就不是完全逆序了所以应该比4n小具体是多少很难算我就不展示了。最后一趟可以算是O(n)。如果不看内部只看预排序的次数就是对数次按上面来看(省略1)就是log以3为底的对数。4.堆排序想要了解堆排序首先要知道向上调整建堆和向下调整建堆以升序为例我们先用向上调整建堆把它建成大堆AdjustUp(a,1)我们从a[1]开始调注意while循环里面是child 0举个例子9要调多次才能到对应位置。其实降序要建小堆升序要建大堆倘若降序建大堆的话如图大堆建好后9相当于排好了不能动后面的数字就要重新建堆这时候你就会发现7和8本来是兄弟重新建堆后变成父子7和5本来是父子重新建堆后变成兄弟关系全部乱了虽然这个思路也能走下去但是建堆的代价太大所以还是按降序建小堆升序建大堆的思路来走。上面我们已经建好了大堆排升序的话我们只需将9和1换个位置然后将9作一个伪删除(将9不看作堆中的数据)再把堆顶的1用向下调整就可以选出次大的数(8)接着将8和堆底的上一个位置交换依此类推。它的效率为(O(n*logn)每次向上调整为logn调整n个数就是n*logn)。还有一种算法是向下调整建堆它的效率为O(n)比向上调整的效率高。它的思路是从倒数的第一个非叶子节点开始调图如下(现在讨论的时间复杂度是建堆的效率):蓝色数字是调整顺序下面我们就来计算向下调整建堆的效率为什么是O(n)。以满二叉树为例(因为完全二叉树节点的调整次数比满二叉树少我们以最坏情况考虑)。因为第h层是叶子节点不用调整所以从第h-1层开始调第h-1层的节点有2^(h-2)个每个节点要最坏调整1次第h-2层的节点有2^(h-3)个每个节点要最坏调整2次依此类推。就可以得到总移动次数F(h) 2^0*(h-1)2^1*(h-2)...2^(h-3)*22^(h-2)*1。不难看出用错位相减即可化简F(h) 2^h-1-h再算一下节点个数N与高度h的关系2^h -1 Nh log(N1)(这里的log是以2为底的不方便敲)带入总移动次数F(n) N-log(N1)约等于O(N)。我们也来看一下向上调整建堆为什么是nlogn。第一层不用调第二层的节点有2^1个每个节点要最坏调整1次第三层的节点有2^2个每个节点要最坏调整2次第h-1层的节点有2^(h-2)个每个节点要最坏调整h-2次第h层的节点有2^(h-1)个每个节点要最坏调整h-1次依此类推。就可以得到总移动次数F(h) 2^1*12^2*2...2^(h-2)*(h-2)2^(h-1)*(h-1)h log(N1)(同上)化简整理得F(n) (N1)log(N1)-2N约等于nlogn。最终堆排序的代码如图因为是从第一个非叶子节点开始调n-1是最后一个节点再减1除2就是第一个非叶子节点不过不管是向上调整建堆还是向下调整建堆最后堆排序都是O(n*logn)因为建好堆后最后一层有N/2个节点它们每个节点都要都要向下调整log(N-1)次它与向上调整建堆的思路是一样的。向下调整建堆的堆排序是O(N)O(NlogN)向下调整建堆的堆排序是O(NlogN)O(NlogN)化简后总的堆排序都是O(NlogN)。5.选择排序选择排序就是将数组遍历一遍选出最小的数放在左边再选出次小的数放在左边也就是暴力遍历我们做一个优化在[beginend]之间遍历一遍选出最小的数和最大的数不过它的效率不管是有序还是逆序都是O(n^2)代码如下:这里有个坑就是当beginmax时min和begin交换后max的值会变举个例子a[4] {9,4,2,8}min和begin交换后变为2,4,9,8这是max就不是9了而是2所以要将min赋给max。6.快速排序快速排序有点复杂我们先来看单趟如图:我们令左边第一个数为key将左边的数给left右边的数给right让right往左走,找比key大的数left往右走,找比key小的数先找到的停一下等另一个也找到后交换如果一边找不到另一边就会一直等直到相遇再和key交换位置这样的话key的左边都是比key小的数右边都是比key大的数然后再排key的左边再按上面的思路。这挺像二叉树的递归思想学过的话更容易理解代码如下:注意一下while循环里面要加beginend否则begin和end相遇后就会错开还有只有递归到一个数的时候才算有序像上面的1和2再递归一次就只剩1也就是left0right1key1就会出现leftright和leftright这两个就是结束条件如上图。它的时间复杂度是O(n*logn)因为单趟大概是在中间位置相遇分区间的话大概也会占一半单趟走一遍是n,递归log次(每次大概左右区间分得差不多一样)所以时间复杂度是O(n*logn)。但是这样写有个缺点就是数据接近有序的时候它的效率会变低因为接近有序时右边找不到小左边很容易找大导致基本上右边要走N次begin与key交换后又很靠近左边所以第二次大概要走N-1次依此类推最后发现它退化成一个O(n^2)的算法了而且递归深了容易导致栈溢出。究其问题的根本就是选key的位置我们希望选的key大概是个中位数现在有两个思路1.选随机的key 2.三数取中(选最左边中间和最右边的数中间就用(leftright)/2)。当然随机值是不可控的我们不予采用下面是三数取中(它大大降低了key取到最小或最大的可能性):可能有人不理解三数取中的逻辑我画个图就好理解了(如果会的读者可以跳过这段)。上面的leftmid就是定了这两个的位置让right往它们当中插入有人可能会说为什么是先往有插再往左插最后往中间插这样逻辑不是很乱吗为什么不从右往左或者从左往右其实不然举个例子如果从右往左插入的话大前提已知leftmid如果你写rightmid你就不知道left与right的关系如果你写leftright你就不知道mid与right的关系所以这样写是有讲究的你也可以写成132(数字是right的插入顺序)第二个midleft也是同理。这样处理后面对有序的情况它的时间复杂度就是O(nlogn)不会退化了。其实到这里我们写的快速排序还有可以优化的地方你想一想当递归到数据很少的时候我们还有必要继续递归下去吗当递归到数据只有5个时它还要走六七次递归。学过二叉树的读者知道(以满二叉树为例)一个高度为h的树他最后一层有2^(h-1)个节点占了总结点数的一半(总节点有2^h-1可以把1省略)倒数第二层占了1/4倒数第三层占了1/8倒数第四层占了1/16如果能优化最后四层效率提升了大概90%所以我们决定当数据量大于10时我们走递归剩下我们走插入排序(因为插入排序的效率实际比冒泡排序和选择排序快)这就是小区间优化注意是aleft因为有左右区间left不一定是0。有人可能还会有疑问为什么left和right相遇的位置一定比key小而且必须让right先走(如果比key大那就没有做到比key小的在它左边比key大的在它右边)首先相遇有两种情况1.left遇right2.right遇left。left遇rightright先走先停下来停下来的地方一定是比key小(因为right找小)left没找到大的就与right相遇了right遇leftright先走没找到比key小的就和left相遇了left停下的地方是上一轮交换完了的位置所以也比key小(有人会问为什么right不能在比key大的地方停下right一直往左走直到相遇因为我们是让right先走所以只有当right停下时left才能走而当right停下也就是遇到了比它小的值left也停下那么就要交换了而right要是不停下最差也是在key的地方相遇然后key和自己交换)。当然非要右边先走也行只需将key挪到右边而不是左边。还有一种排单趟的方法挖坑法就是先把key(我默认在左边)的值放在一个临时对象里这就形成了一个坑再让右边先走找小找到后放在坑里这样又形成了一个坑然后让左边走找大找到后放到坑里依此类推最后left和right会在坑相遇这样写就不用考虑为什么右边先走(因为左边挖了坑要让右边填上)也不用考虑为什么相遇的位置比key小(因为在坑相遇不用考虑)还不需要用交换代码如下:还有一种是前后指针法令prev leftcur prev1当cur key时我们就把prev然后交换a[prev]和a[cur]再cur为了防止自己与自己交换prev ! cur。当cur key时cur。最后交换a[key]和a[prev]的值。代码如下:小结一下我们现在看了三种单趟的方法:1.hoare法(也就是)2.挖坑法3.前后指针法不过它们三个的效率都是O(n)。不过递归有栈溢出的风险我们可以尝试写非递归这时候就要借助栈或队列栈的“后进先出”模拟递归很像(像深度优先遍历)所以我们来用栈模拟实现非递归代码如下这里我就不展示栈的增删查改了我们来看一下它的逻辑就是用下标来控制区间不是将数组里的数据往里面入它入就是入begin和end两个下标排序就是Quicksort3来控制我画一张图来解释一下:箭头的意思是出栈顺序先入9(因为栈是后进先出所以先入9后面同理)出9再入0出0key为5入9入6入4入0再出0出4依此类推。7.归并排序归并排序用的也是递归思想我们先看代码:它的核心是在第二个函数第一个函数开一个额外数组第二个函数也是要用下标分割空间当递归到只有一个数时才算有序我画一个图方便理解:它是先走0~90~40~10~0再走1~12~23~4右半部分逻辑一样我就不画了。它有点像二叉树的后序遍历。最后把数排好后再拷贝回原来的数组。它的时间复杂度是O(nlogn)层数是logn层每层处理n个数所以是nlogn它的空间复杂度是O(n)因为开了一个额外数组。我们再写一下非递归如果用栈来存放的话需要开两个栈所以我们用循环来写代码如下:写非递归要注意边界它的思路相当于是从递归的最后一层开始如图[0,0][1,1]...gap是先一一归并再二二归并再四四归并...这是gap的作用但是这样写有越界风险换一组数据如图:这一组数据有十个数后三排都有越界由图可知begin1不越界end1begin2end2有可能越界当end1越界时其他两个一定越界当begin2越界时end2一定越界所以分两种情况begin2是否越界end2是否越界(有人可能会问为什么不管end1看图[811]就是end1越界情况这时[811]有效数据只有下标89又因为89在上面已经排好所以直接break即可不管end1是否越界只要begin2越界就要这么处理)end2越界只需将end2改为n-1即可。8.计数排序计数排序的逻辑是统计数据出现的次数我们先看代码:它首先选出数组中的最小值和最大值作差后就可以选出它的范围进而确定开多大的空间(有人可能感到疑惑要是有重复的数据空间不就开小了吗)其实我们开的这个temp数组只是为了统计数据出现次数最后再覆盖原数组。但是如果排的数据从100~109难道要开109个空间吗当然不用我们可以将100看成0109看成9即相对映射也就是a[i]-min不过记得最后imin把数据还原。它的时间复杂度是O(nrange)要是n与range差不多大那么即为O(n)效率很高但缺点也很明显就是只适合排数据比较集中的数据是整数。9.基数排序它的核心思想就是按百位十位个位这种位数来排它是先排个位再排十位再排百位依此类推但是有了计数排序它就显得很鸡肋了因为它不能排负数计数排序可以它只适合都是百位数或者都是十位数等等而且计数排序的缺点它也有只适合排数据比较集中的数据是整数。我们只了解就行了。10.桶排序它的核心思想就是创建一个指针数组但是数组的下标永远都是0~9而且最高位是几就挂几号桶后面是用链表连接连到链表的数据还要排序可以走一个插入排序它只适合数据比较均匀如果不均匀比如都在一个桶就没意义了。总结我们把重要的七大排序总结一下首先把稳定性的定义说一下值相等的两个元素排序完成之后它们原来的先后顺序保持不变。举个例子[12(a)2(b)]这是排完前的顺序稳定排序排完[12(a)2(b)]a还在b的前面不稳定排序排完[12(b)2(a)]a,b的位置颠倒了。稳定排序我就不解释了我们看为什么其他几个排序为什么不稳定希尔排序(相同的数分到不同的组无法控制)堆排序(如果是[221]建堆再排序后堆顶的数与堆底交换第一个2就跑后面去了)选择排序([221]把最小的1与2交换后第一个2就跑后面去了)快速排序(分组也无法控制)最后归并排序的空间复杂度为O(nlogn)递归与temp都要开空间只不过将logn省略了。其实我们可以发现涉及交换的排序大多是不稳定的。感谢大家的阅读。