红黑树最坏情况下删除节点复杂度_快速排序最好最坏时间复杂度

万字长文丨深入理解排序算法 　　一、排序算法的基本逻辑 　　排序是数据结构与算法里面最基础最入门的内容，虽然简单，但是深入研究的话里面还是有很多内容的，今天我们来全面详细的讲一讲各种排序算法的分类、原理、复杂度、稳定性和实现方法。 　　1.1 什么是排序 　　我们先来说一说什么是排序、为什么要排序。什么是排序，这个很简单，就是把无序的东西按照一定的规则顺序排列成升序或者降序。为什么要排序，有两个原因，一是为了方便后面的查找，如果没有排序的话只能进行线性查找，时间复杂度是O(n)，如果排序了就可以进行二分查找，时间复杂度是O(logn)，复杂度一下子就大大降低了。我们来说明一下这两种复杂度的差别有多么悬殊(虽然用词错误，但是这么用确实很符合气氛)，假设n是10亿的话，O(n)还是10亿，而O(logn)是30多(以2为底，假设系数是1)，30多和10亿比都可以忽略不计了。二是为了显示的时候按照顺序显示，人类的习惯就是喜欢看有序的东西。 　　1.2 排序算法分类 　　那么该怎么进行排序的呢，最基本的方法是什么呢，最基本的方法那当然是比较了，不比较怎么排序呢，只有比较了才能知道该谁前谁后。可是当我看到很多算法书上都说排序有比较排序和非比较排序，我第一眼看到的时候都惊呆了，不可能，绝对不可能。非比较还能排序，排序还能不比较，这怎么可能，绝对是瞎扯。当我继续看下去的时候发现确实能。后来我仔细思考了一下发现，非比较排序本质上还是在比较，只不过它们不是在和别人比较，而是在和自己比较，在和自己的本位比较 (突然想起了上学时老师经常说的话，不要老是和别人比，要多和自己比，非比较排序做到了)。什么是和自己的本位比较呢，比如说有1到9共9个数顺序是乱的，1本来就该在1的位置，2本来就该在2的位置，……，9本来就该在9的位置，它们不用去和别人比，只需要去站到自己本来应该站的位置，顺序就自然就排好了。所以比较排序、非比较排序也可以叫做显式比较排序、隐式比较排序。 　　1.3 比较排序 　　光比较还不行，谁给谁比较呢，比较了之后怎么做呢，这些做法的不同又产生了很多不同类型的比较排序方法。同样，隐式比较也存在这些问题，怎么找到它们的本位呢，它们站到本位之后又该怎么办呢，这些做法的不同又把非比较排序分为了很多的类别。我们先说比较排序，我们最容易想到的做法就是选择排序，先选一个最高的站在第一位，在从剩下的选择一个最高的站在第二位，以此类推，到最后一个的时候就已经从高到低排好序了，我们上学时排队也会经常用到这种方法。还比较容易想到的另一个方法就是插入排序，先随便过来一个人，再过来一个，比他高就站到他前面，比他低就站在他后面，再过来一个人，如果比前面的高就一直往前面走，直到不比前面的高就不走了，就在这个位置插入，这种排序方式上学排队的时候也有用到过。还有一种比较常见的排序方式是交换排序，在军训的时候很常用，教官突然叫集合，大家匆匆忙忙的站成一排，教官说从左往右从高到低排列，大家左右互看，你看看我我看看你，比左边的人高就和左边的人交换，比右边的人低就和右边的人交换，不一会就排好序了。比较排序中，我们已经说了选择排序、插入排序、交换排序三种方法，这三种排序都是很直观很容易想到的，生活中也很是很常用的。比如我们打牌的时候会把手里的牌排成一定的顺序，有人习惯用插入排序法，有人喜欢用选择排序，也有人喜欢用交换排序。还有一种排序方法，是不容易想到的，生活中很少有用到，叫做归并排序。它的大概逻辑是先两个人一对两个人一对的，两个人之间先排好序，然后两对人再合并成一队并排好序，以此类推，直至所有人都排成一队，也就排好序了。我们后面讲到归并排序的时候会再具体讲它的逻辑。 　　视频讲解 　　通俗易懂的红黑树,B树,B+树 本质区别及应用场景（上） 　　通俗易懂的红黑树,B树,B+树 本质区别及应用场景（下） 　　LinuxC++后台服务器开发架构师免费学习地址 　　【文章福利】：小编整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！~加入（需要自取）

　　1.4 非比较排序 　　我们举例说明了比较排序的几类操作逻辑，那么非比较排序是怎么操作的呢。我们前面说了可以让数据直到站到它们的本位去就排好序了，但是这里面有一个条件，就是数据要是不重不漏的。很多时候数据都是有重有漏的，怎么办呢，这时候我们有一种方法叫做计数排序。我们举例说明一下什么是计数排序，比如1,5,9,6,5,2,6,7,5这个数列有9个数，能不能它们直接站到本位去呢，不能，因为5这个数有3个，6这个数有两个，让所有的5都站到第5位上是站不下的，同时3,4这些位上是没有数的，因此要先对这些数进行计数，如果有一个1，就站到1位上，如果有两个1就站到1,2位上，如果没有1,1位就空着留给下一个数。假设有两个1，再看2，如果有一个2,2就要站在3位上，如果有两个2，2就站到3和4位上，如果没有2，3位就空着留给下一个数。以此类推排序3,4,5…9，整个数列就排好序了。 　　计数排序适合那些数据分布比较集中的情况，如果数据比较分散，再用计数排序就比较繁琐了，比如有10个数15,23,78,56,3,67,52,23,99,11，它们的范围大小是0–99，此时用计数排序的话是需要统计1出现的次数，2出现的次数，……，98出现的次数，99出现的次数，这就很费事了。对于这种情况，我们想出了一个办法，就是桶排序，先准备10个桶，0-9放到第一个桶里面，10-19放到第二桶里面，……，90-99放到第十个桶里面，然后每个桶里面进行排序，具体排序可以选择插入排序、选择排序或者其他排序方法都可以，然后再从10个桶里面依次把数收回来，这样整体上就排序了。如果数据特别多还可以采取多级桶排序，比如要是有100个数，范围是0-999，就可以采取二级桶排序，先用大桶，0-99一个桶，100-199一个桶，……，900-999一个桶，一共10个大桶，大桶里面再用小桶，10个数的范围为一个小桶。先在小桶里面排序，然后把一个大桶里面的所有小桶的数收起来，再把所有大桶的数收起来，这样就排好序了。 　　非比较排序中还有一种排序，叫基数排序，基数排序比较复杂，也不太好理解，我们先简单地讲讲。基数排序只能用于非负整数的排序，基数排序是按位数进行多轮排序的，按照个位十位百位千位的次序进行多轮排序，先按照个位进行排序，再按照十位上的数字进行排序，……，直至到最高位，每一轮的排序方法都要选择稳定排序方法，最后顺序就排好了。大家可能有两个疑问，为什么要从个位进行排序，不从高位往下进行排序，为啥从低位开始排序结果会是正确的呢。先说第一个疑问，为啥不从高位开始，如果从高位开始排序的话，那么这么排下去，最后的结果就是乱序的，比如说有四个数501,312,457,562，降序排序，先排百位，501,562,457,312，再排十位，562,457,312,501，再排个位，457,562,312,501，结果完全错了。为啥错了呢，这是因为十位会打乱百位的排序，个位会打乱十位的排序。如果想要结果正确的话，就需要我们进行局部排序，不是所有的十位在一起排序，而是百位相同的数十位一起排序，百位不同的数它们之间十位就不排序了。所以你还要添加数据记录这些情况，这样这个排序就变成了2级桶排序了，就不是基数排序了。而桶排序的麻烦点就在于，桶的操作是比较复杂的，因为每个桶放入多少个数据是不确定的，所以桶排序一般都要使用链表结构。基数排序就是要避免桶的操作。我们再来说第二个疑问，为啥从低位到高位排序是正确的，501,312,457,562，先排个位，457,312,562,501，再排十位，562,457,312,501，再排百位，562,501,457,312，最终结果是正确的，为什么是正确的呢，个位排好之后，排十位，十位不同的，把值大的排到前面，这没有问题，不用考虑个位的问题。如果十位相同，十位相同的数会集中到一起，由于这是稳定排序，个位的相对位置还会保留着，所以个位大的还在前面，十位相同个位大的在前面，排序是正确的。再排百位，也是同理，百位大的排到前面，不用看十位个位的大小如何，百位相同的数会集中排在一起，它们的十位个位就很关键了，由于上一轮它们的十位个位的顺序就排好了，这一轮也是稳定排序，所以十位的相对位置不变，所以最终排序就是正确的。 　　我们再来看一下计数排序、桶排序、基数排序，这三者之间的关系，计数排序可以看做是特殊的桶排序，相当于是桶数特别大的桶排序，桶数大到一个数值一个桶。基数排序其实和其他两者没有啥关系，但是如果基数排序每轮的排序方法都用计数排序的话，并且只有一轮的话，那么基数排序在这种情况下就是计数排序了。基数排序和桶排序之间就没有啥关系了，如果非要硬扯上关系，只能说它们在一些特定的情况下都可以看成是计数排序，注意这仅仅是逻辑上能看成，并不是，因为计数排序没有桶的概念，也没有轮的概念，而桶排序必须要有桶，基数排序必要从从低位到高位进行多轮稳定排序。（有的书上把按位数进行多轮排序都叫做基数排序，把从高位往低位排序叫做MSD基数排序，这种排序要分桶，实际上就是桶排序，把从低位往高位排序叫做LSD排序，也就是狭义上的基数排序。这种分类方法并不好，MSD和LSD并没有相似性，前者需要分桶，后者需要内层排序是稳定排序，这样叫只会导致概念的混乱性，让人更难以理解。所以我们采取更普遍的叫法，桶排序就是桶排序，基数排序就只能从低位开始排序） 　　1.5 排序算法评价维度 　　一个排序算法的好坏，我们该怎么去评价呢，有哪些评价维度呢。我们可以从算法复杂度、位置稳定性、适用性三个维度来评价。 　　算法复杂度可以分为时间复杂度和空间复杂度，时间复杂度又分为最好时间复杂度、最坏时间复杂度和平均时间复杂度。复杂度是算法输入规模与执行规模之间的函数，复杂度的表示方法是大O表示法，常见的复杂度有O(1) 常量复杂度, O(logn) 对数复杂度, O(n) 线性复杂度, O(nlogn) 对数线性复杂度, O(n2) 平方复杂度, O(n3) 立方复杂度,O(2n) 指数复杂度, O(n!) 阶乘复杂度。关于复杂度理论，大家可以去看一些专业的书籍来学习，比如《算法导论》，这里就不多讲了。空间复杂度是指排序算法为了排序而额外分配的辅助内存有多少，大部分排序算法额外分配的内存并不多，多数为O(1)，而且现在的计算机内存都非常多，所以一般情况空间复杂度不太重要。时间复杂度是评价一个算法的重要标准，最好时间复杂度是在最好的情况下算法的时间复杂度，比如数组已经排好序了，最坏时间复杂度是最坏的情况下算法的时间复杂度，比如数组完全逆序的情况下。最好最坏都是极端情况下的特殊情况，一般不太重要，重要是平均时间复杂度，它是所有情况下的平均值，也是一般情况下的复杂度，所以平均时间复杂度是评价算法的一个重要维度。 　　我们所说的排序算法的稳定性是指位置稳定性，不是程序的稳定性(程序有没有BUG会不会崩溃啥的)，而是两个数值相等的素在排序前后的相对位置会不会改变，这对于整数来说可能看不出来，也没啥意义，但是对于结构体来说就能看的出来，而且很有意义。比如我们要对struct student 进行排序，要求按照年龄排序，年龄相同的按照身高排序，我们就可以先进行身高排序，再进行年龄排序(稳定排序)，这样就能达到目的了。如果年龄排序的方法不是稳定排序，就会把身高的相对性打乱，就没有达到我们的要求。 　　算法的适用性也很重要，比如非比较排序的时间复杂度都很好，都是线性复杂度或者接近线性复杂度，但是非比较排序的适用条件比较苛刻，很多情况下不太适用。 　　1.6 比较排序的高级算法 　　讲完了排序算法的评价维度，我们知道时间复杂度是一个很重要的维度，那么比较排序算法的最好的时间复杂度是多少呢，能不能小于O(nlogn)呢，我们是不是还有啥新的排序算法没有发现呢？根据决策树模型我们可以计算出来比较排序算法最好的时间复杂度是O(nlogn)，不可能比这个再好了，具体原因大家可以去看《算法导论》8.1节。我们前面讲的选择排序、插入排序、交换排序的时间复杂度都是O(n2) ，归并排序的时间复杂度是O(nlogn)，对于前三种，其时间复杂度大于O(nlogn)，我们有没有办法优化算法，使其达到O(nlogn)或者接近O(nlogn)呢，有，对于选择排序，我们优化后的算法叫做堆排序，相应的把之前的算法叫做简单选择排序。堆排序也是每次都选择一个最大值放到最后一位，但是它选择最大值的方法和简单选择排序不同，它利用了堆这个数据结构，堆能保留之前比较的结果，所以可以减少比较次数，从而达到优化性能的目的。对于交换排序，我们优化后的算法叫做快速排序，之前的算法可以叫做简单交换排序，业界都叫做冒泡排序。冒泡的问题在于只能相邻的素做比较并交换，一个数据每次移动的位置只有一位，效率很低。快速排序采取的方法是选取一个素作为key，每个人都和它进行比较，比它小的都移动到它左边，比它大的都移动到它右边，这样就大大的提高了移动的效率。对于插入排序，优化之后的算法叫做希尔排序，之前的算法叫做简单插入排序。插入排序的特点是它对接近排序的序列效率特别高，对于比较杂乱的序列效率就要低很多。希尔排序利用了插入排序的这个特点，它先对整个数组进行分组插入排序，当分组数比较多的时候，一轮分组插入排序的效率是接近O(n)的，然后逐步降低分组的数量进行插入排序，最后当分组数为1的时候，也就是整个序列就分为一个组，就是直接插入排序了，此时整个数组比较接近排序状态，插入排序的效率很高。这几个算法的逻辑都非常复杂，这里只是简单介绍一下，第二章里会进行详细的讲解。 　　1.7 递归性与原地性 　　排序算法的实现还有两个特征，递归性和原地性。递归性，一个算法实现是否是递归实现。原地性，算法是否在原地排序，还是分配了临时空间把原数据腾挪过去进行排序。这两个特点为什么不放到算法评价里面去说呢，因为我们对算法进行评价时并不太在意一个算法是否是递归的，是否是原地排序，这两点是算法的属性，是算法自身的实现逻辑所决定的。算法的评价维度是我们比较在乎的点，我们比较在乎的是算法的效率，包括时间效率和空间效率，也就是算法的时间复杂度和空间复杂度，我们有时候也在乎算法的稳定性，因为我们有时候需要算法稳定，算法的适用性我们也在乎，因为如果你的算法不适用于我们的数据，我们也用不了这个算法啊。但是我们很少会说我们需要一个排序算法它必须是递归的或者原地的，这听起来有点莫名其妙。所以递归性和原地性我们不放入算法的评价维度中，我们把它叫做算法的实现特征。 　　1.8 排序算法概览 　　现在我们对排序算法的分类、操作逻辑、评价维度都有了基本的了解，下面我们画个简单的图，先对本文要讲的所有排序算法有个大概的认识。

　　大家此时不必想着要对这个图进行完全的理解，有个大概的印象简单的理解就行。下一章我们会用C语言对每一个算法进行实现，并会具体分析它的实现逻辑以及它的复杂度和稳定性等，到本文结束的时候你对这个图可能就理解比较深刻了。 　　二、排序算法实现与分析 　　本章用C语言实现每个排序算法，一个算法一个小节，每个小节的内容依次是算法简介、算法描述、C语言实现、代码分析、算法总结、时间复杂度、空间复杂度、稳定性、递归性、原地性。 　　本文所有示例代码都使用升序排序 　　2.1 如何分析排序算法 　　如何计算一个算法的时间复杂度和空间复杂度呢，这里面有严谨的数学和严密的逻辑，想要学习的同学可以去研究相关的专业书籍，本文会使用比较直观好理解的，但是不太严谨的方法进行分析。 　　我们先说时间复杂度，对于大部分算法来说，一般都是内外双重循环结构，外循环的复杂度一般都是O(n)，内循环复杂度和外循环复杂度的乘积就是整个算法的复杂度。内循环复杂度有几种情况，如果内循环复杂度每轮都是个固定值，那就很简单，比如内循环总是循环n次，那么内循环复杂度就是O(n)，算法的复杂度就是O(n2)。如果内循环的复杂度是O(logn)，那么算法的复杂度就是O(nlogn)。但是很多时候内循环的执行次数往往是变化的，有的是递增序列从1到n，有的是递减序列从n到1，此时我们可以算一下内循环的平均执行次数，(n+1)*n/2/n = 0.5n+0.5，忽略常量和系数，内循环的复杂度就是O(n)，此时算法的复杂度就是O(n2)，这种情况比较常见。还有一些特殊情况，对于有些特殊数列，内循环的条件执行一次就结束了，内循环的复杂度就是O(1)，所以算法的复杂度是O(n)。还有一种情况是内循环第一轮执行了n次，外循环一次就结束了，此时算法复杂度也是O(n)。 　　对于递归算法来说，要看它的递归树层数和每层的时间复杂度，我们画个图看一下。

　　我们可以看到每一层的数据规模之和都是n，而树的高度一般是logn，所以递归算法的时间复杂度一般都是O(nlogn)，只要树别退化成线性结构。如果退化了，树的高度就是n，那么算法复杂度就变成了O(n2)了。 　　我们再来看空间复杂度，如果我们分配的变量是简单变量，与输入规模n无关，那么这个变量本身的空间复杂度就是O(1)，如果它分配在外层循环里，它的复杂度并不会乘以n，因为循环的每一轮它都销毁重建了，它并不会累积。如果它出现在内循环里，它的复杂度既不会乘以n，更不会乘以n2，这点可能难以理解。我们先只看内循环，和刚才讲的道理一样，它一直在销毁重建，所以复杂度还是O(1)，再把内循环当成一个整体，它在外循环里也是不断地销毁重建，所以复杂度还是O(1)。所以对于双重循环结构来说，只要定义都是简单变量，空间复杂度就一定是O(1)，推广一下对于任意n层循环也是如此。 　　递归调用的空间复杂度最好的情况也至少是O(logn)，这是因为递归调用是要传递参数的，参数会不停地压栈一直到递归树的最深处，所以空间复杂度至少是O(logn)。如果在递归前定义了简单变量，效果和参数是一样的，空间复杂度还是O(logn)。如果在递归调用后面定了简单变量，则这个变量不会累积，空间复杂度是O(1)，如果定义的不是简单变量，而是和输入长度n相关的数组变量，则其空间复杂度是O(n)。 　　如何判断一个算法是不是稳定的呢？非原地算法一般都是稳定的，或者可以实现成稳定的。而原地算法要想实现排序就必须交换素，如果算法只交换相邻的素，那么算法一定是稳定的，假设一个数列里面有两个5，把前面的叫做A5后面的叫做B5吧，B5要想跑到A5前面就必须先不停地交换到紧挨着A5，然后再和A5进行交换，但是排序算法都是在数据大于或者小于的时候才可能进行交换，A5等于B5，是不会执行交换的，所以B5不可能跑到A5前面，所以只交换相邻素的算法一定是稳定算法。如果算法可能交换不相邻的素，比如B5和A5前面的3交换了，那么A5和B5的顺序就交换了。注意必须在任何情况下都稳定才能叫做稳定排序，只要有一种情况下不稳定那就是不稳定排序。交换不相邻素不一定能导致这个数列的排序结果不稳定，但是一定存在一个数列它的排列结果是不稳定的。所以，交换不相邻素的排序是不稳定排序。 　　原地性与递归性从代码里一眼就能看出来，不用分析。 　　2.2 简单选择排序 　　简单选择排序是最简单最直接的排序方法，先通过全员比较找到最小的那个值放在首位，然后排除首位，在剩余的数里面全员比较放到剩余的首位，以此类推，直到所有素都排好序。 　　算法描述： 遍历整个数组[0-n)，通过比较找到最小的数，放在第0位，再遍历[1–n)，找到最小的数，放在第1位，再遍历[2-n)，找到最小的数，放到第2位，……，直到遍历[n-2,n)，找到最小的数，放到第n-2位，排序完成。 　　C语言实现： 　　代码分析： 通过双重循环，外循环从0遍历到nr-2，外循环确定内循环的起点，内循环从外循环的i+1遍历到nr-1，外循环中定义 min = i，先假定内循环的起点就是最小值，内循环中，不断去与之前记录的最小值的下标所对应的值进行比较，如果发现有更小的值，则更新最小值下标为j，内循环结束后，min代表当前轮中最小值的下标，通过tmp变量交换arr[i]与arr[min]，把最小值交换到当前轮的首位。外循环结束，整个序列就是升序排序了。 　　算法总结：双重循环，同向而行，外循环右缺，内循环左缺。(同向而行指的是内外循环的index都是++或者–，右缺指的是index值到nr-2，左缺指的是内循环的index是外循环的index+1，下同，不再赘述). 　　时间复杂度：外循环是O(n)，内循环是递减序列是O(n)，所以算法复杂度是O(
)，内外循环的执行都是必然的，不存在特例，所以最好最坏平均时间复杂度都是O(
)。 　　空间复杂度：双重循环，只定义了一个简单变量，所以空间复杂度是O(1)。 　　稳定性：每次交换素时都很大可能交换的是不相邻素，所以简单选择排序是不稳定的。 　　递归性：非递归。 　　原地性：原地。 　　2.3 堆排序 　　堆排序是利用堆这种数据结构进行排序的一种算法。堆是一个近似完全二叉树，并且对于大顶堆来说每个子节点的值都小于等于它的父节点，对于小顶堆来说每个子节点的值都大于等于它的父节点。堆排序是对简单选择排序的一种优化，简单选择排序的问题在于它的比较次数太多，因为它每次比较完一遍之后只留下了最小值下标信息，其他比较信息都丢了，导致比较次数是O(n2)。堆排序利用堆的数据结构，每次选择出来一个最大值之后，之前的很多比较数据还保留在堆结构中，从而减少了比较次数。堆排序的总体逻辑和简单选择排序差不多，我们以大顶堆升序排序为例说明，先把数组建立为大顶堆，然后把堆顶也就是0号素和最后一位素交换，然后把[0 – nr-2]看做一个堆重新建立大顶堆，此时0号素又是最大值，和nr-2位置交换，然后再缩小堆的范围，再重建大顶堆，再把堆顶和nr-3交换，以此类推，直到堆顶和位置1交换，整个数组就排序完成了。堆排序的难点在于理解堆的数据结构，在于理解是如何建堆和调堆的。 　　堆是一个树状结构，但是却是用数组表示的，它的节点连接是隐含在下标中的。每个节点(根节点除外)的父节点都等于自己的(index-1)/2，每个节点的左子节点(如果存在的话)等于自己的 index2 + 1，右子节点(如果存在的话)等于 index2 + 2。如下图所示，可以帮助我们理解堆的结构，把堆的数组结构转化拆分为树形结构，可以很清楚地看到堆的父子节点之间的下标的关系。

　　算法描述： 算法的第一步是要建立大顶堆，我们接着上图讲述如何建立大顶堆。堆的建立是从最后一个非叶子节点开始调堆，一直往前调，直到最后对根节点进行调堆，然后大顶堆就建成了。最后一个非叶子节点就是最后一个叶子节点的parent，也就是 (nr-1)/2 == nr/2 – 1，对于图中来说就是index 4，也就是说对index 4, index 3, index 2, index 1, index 0，依次调堆，这个大顶堆就建成了。为什么要从下往上调堆呢，因为只有子树是合格堆了再对自己调堆，才能保证自己和子树都是合格堆。如果子树不是合格堆而堆自己进行调堆的话，是不能把自己调成合格堆的。调堆的逻辑是，先看自己的左子和右子谁大，谁大就和谁交换值，这样自己就是三者之间的最大值了，同时又因为左子和右子都是合格堆，所以左子是左子树的最大值，右子是右子数的最大值，所以自己现在是自己树上的最大值，自己就是个合格堆了，被交换的左子或者右子此时就不一定是合格堆了，所以再对其进行递归调堆。整个调堆过程如下图所示：









　　调堆完成之后，把堆顶和最后一个素互换，最后一个素就是最大值了。再把[0 – nr-2] 看成一个堆，此时index 1 和 index 2 都是一个合格的大顶堆，只有index 0 不是，因此只对 index 0 进行一次调堆就可以了。如下图所示：





　　至此我们已经把最后两个素排列好了，以此类推，不停地对index 0调堆，与当前尾素互换，直至最后就能把整个数组排列好。 　　C语言实现： 　　代码分析： 首先有个辅助函数heap_adjust就是用来调堆的，它的操作逻辑就是上图中所说的调堆逻辑。主函数heap_sort，第一个for循环建立大顶堆，从最后一个非叶子节点开始依次调堆，直至对index 0进行调堆，整个大顶堆就建立完成了。第二个for循环，先把堆顶也就是index 0和当前的堆尾进行交换，然后对index 0进行调堆，此时传递堆大小是length，也就是堆尾是length-1，也即是把刚才的堆尾排除在外了。第二次循环，先把length–，此时index 0是个合格的大顶堆，再把index 0 和堆尾交换，然后再对index 0 进行调堆。循环执行完之后，整个数组就是升序排序了。 　　算法总结：两个for循环，第一个for循环建立大顶堆，循环范围是[nr/2-1 – 0]，第二个for循环不断地交换堆顶和尾素，并重建大顶堆，循环范围是[nr-1 – 1]。 　　时间复杂度： 先看heap_adjust的时间复杂度，它的操作次数就是树的高度，所以复杂度是O(logn)，第一个for循环执行了nr/2 个 heap_adjust，所以时间复杂度是O(nlogn)。第二个for循环是nr个heap_adjust，时间复杂度也是O(nlogn)，两个O(nlogn)加起来还是O(nlogn)，所以堆排序的时间复杂度是O(nlogn)，没有什么特殊情况，所以最好最坏平均时间复杂度都是O(nlogn)。 　　空间复杂度：两个双重循环，只定义了几个简单变量，所以空间复杂度是O(1)。 　　稳定性：大部分操作都是非相邻素交换，所以堆排序是不稳定的。 　　递归性：非递归。 　　原地性：原地。 　　我们可以发现，简单选择排序和堆排序有几个共同点： 　　1.最好最坏平均时间复杂度都是相同的，不存在特殊的排序情况 　　2. 空间复杂度都是O(1) 　　3.两者都是不稳定排序 　　2.4 简单插入排序 　　简单插入排序的方法是逐步构建已排序序列，把未排序区的素一个一个地往排序区插入，在排序区里面从后往前搜索，找到自己的位置并插入，它之后的素各往后移动一位，当未排序区的素清空时，排序就完成了。简单插入排序在素数量少时是一种非常高效的排序。 　　算法描述： [0 – 0] 是已排序区，[1 – n-1] 是未排序区，把1号素插入已排序区，根据大小插在0号素之前或者之后，形成新的排序区[0 – 1]和未排序区[2 – n-1]，再把2号素根据大小插入排序区，可能在0之前，在0和1之间，或者1之后，形成新的排序区[0 – 2]和未排序区[3 – n-1]。一直如此操作，直到未排序区变为空集，排序完成。 　　C语言实现： 　　代码分析： 外层循环表达的是未排序区，index从1开始，到nr-1结束，初始排序区是[0 – 0]，就一个素，肯定是已排序的。取未排序区的第一个数作为待插入数，保存在局部变量key中，未排序的首位空间转换为已排序区的空间，根据key扫描已排序空间，比key大的都右移一位，直到遇到不比key大的数值为止。内循环结束后，j的值就是key要插入的位置，这个位置之前的值都小于等于key，之后的位置都大于key。执行arr[j] = key，完成插入。外循环结束后，未排序区为空，排序成功。 　　算法总结：双重循环，背道而行，数据不断右移为key腾挪位置，直到找到key应该在的位置，最后插入。 　　时间复杂度： 外循环复杂度是O(n)，内循环的执行次数是有条件的，假设条件总成立，也就是数列是逆序的情况，内循环的复杂度是O(n)，所以最坏时间复杂度都是O(
)。假设内循环的条件总是不成立，也就是数列已排序的情况，内循环的复杂度是O(1)，所以最好时间复杂度都是O(n)。平均情况也就是一般情况，内循环里面的操作有一半的概率会执行，也就是最坏情况的一半，所以平均时间复杂度还是O(
)。 　　空间复杂度：双重循环，定义了两个简单变量，所以空间复杂度是O(1)。 　　稳定性：逻辑上可以看成是key不断地和前面的素进行交换，也是属于只交换相邻素，所以简单插入排序是稳定的。 　　递归性：非递归。 　　原地性：原地。 　　简单插入排序和简单选择排序对比一下，最好时间复杂度，前者是O(n)，后者是O(
)，平均时间复杂度虽然都是O(
)，但是前者的系数是1/4，后者的系数是1/2，稳定性，前者稳定，后者不稳定，所以简单插入排序完胜简单选择排序。 　　2.5 希尔排序 　　希尔排序是对简单插入排序的一种改进，又叫做缩小增量排序，也叫分组插入排序。它对插入排序的改进是基于插入排序的两个特点，1是插入排序对于越接近排好序的数列效率越高，2是插入排序一般情况下是低效的，因为内循环一次只能把数据移动一位。针对插入排序的特点和缺点，我们可以这样改进它。对数列进行分组插入排序，比如先分5组分别进行插入排序，再分3组分别进行插入排序，再分1组也就是不分组进行插入排序。也就是说希尔排序最后要进行一次插入排序，你也许会觉得之前就进行了很多次操作，最后还要进行一次插入排序，效率肯定比插入排序差。但是这是不对的，因为插入排序的效率受它的输入数据的有序性影响很大，如果输入数据是已经排序的，那么插入排序的效率就是O(n)，输入数据越接近已排序，插入排序的效率就越接近O(n)。前面的分组插入排序就是为了使整个数组更接近排序状态。它是第一个突破O(
)的算法。 　　算法描述： 增量d是一个递减序列，最后递减为1，d序列的选择并不是一个绝对的事情，一般会选择为初始值为nr/2，并不停地除以2。d序列应该尽量使同一组的数不再分配到同一组，也就是d序列要尽量避免16,8,4，2,1，这种序列，因此我们每次都 d |= 1，把d变为奇数。假设nr是10，d第一次是5，进行5组插入排序，0,5一组，1,6一组，2,7一组，3,8一组，4,9一组，分别进行插入排序。第二次d是3，0,3,6,9一组，1,4,7一组，2,5,8一组，分别进行插入排序。第三次d是1，进行简单插入排序。 　　C语言实现： 　　代码分析：三重循环，最外层循环，是d增量循环，从nr/2开始，每次减半，到1停止。内层两层for循环是标准的简单插入排序算法，加入了分组考虑。 　　算法总结：三重循环，外层循环是d增量每次减半，内两层循环是简单插入排序。 　　时间复杂度： 希尔排序的时间复杂度是和增量序列有着密切的关系的，最好时间复杂度可以达到O(n)，最坏时间复杂度可以到O(
)，如果按照Sedgewick提出的增量序列，最坏时间复杂度和平均时间复杂度可以达到O(n1.3)。目前数学上还没有证明希尔排序的最坏时间复杂度的下限是多少，因为不太好证明哪个增量序列是最优的，不太好计算平均情况。 　　空间复杂度：三重循环，只定义了两个简单变量，显然空间复杂度是O(1)。 　　稳定性： d不为1的时候发生了不相邻素交换的情况，所以希尔排序是不稳定的。 　　递归性： 非递归。 　　原地性：原地。 　　2.6 冒泡排序 　　冒泡算法的逻辑是从一端走向另一端的过程中，不断地比较相邻的素，把较小的或者较大放到前面，这样一遍下来之后，最小值或者最大值就到了数组的某一端，把这个值扣除，剩下的数组素再按这个逻辑走一遍，次大的数又浮动到一端了，一直这样下去，数列就排序好了。 　　算法描述： 我们以升序排序向左浮动为例进行讲解，不断的进行(nr-1, nr-2),(nr-2, nr-3),……,(2, 1),(1, 0),比较并把较小值往前交换，这样一轮下来，最小值就到了位置0了。然后下一轮进行(nr-1, nr-2),(nr-2, nr-3),……,(2, 1)比较并把较小值往前交换，把剩余的数中最小值交换到了位置1，然后再进行(nr-1, nr-2),(nr-2, nr-3),……,(3, 2)比较并交换，直到最后一轮进行(nr-1, nr-2)比较并交换，这样整个数列就排序好了。这个过程很像气泡往上冒泡的过程，所以就叫做冒泡排序。 　　C语言实现： 　　代码分析： 双重循环，外层循环控制每次冒泡的顶端，从0往nr-1方向不断地压缩空间，内层循环从最低端往上冒泡，冒泡的顶端被外层循环的index控制。内层循环比较后面的值和前面的值，如果后面的值较小，就把它交换到前面去。这个算法采取了一个优化，就是外层循环index的递进不再是++了，而是内层循环最后一次交换的下标值pos。pos是每轮最后一次发生交换的下标值，代表着剩余区间的所有素都比这个pos之前的值要大，下一次冒泡的顶端就没有必要超过这个pos了。 　　算法总结：双重循环，相向而行，相邻比较，顺序不对就交换。可以简单总结为 邻换对开 四个字，邻换，只有相邻的素才会进行比较并有可能交换，对开，内外循环的index的增加方向是相反的。 　　时间复杂度： 我们这个冒泡排序是优化版的冒泡排序。最好的情况是已排序的情况，第一轮的时候，内循环执行了nr-1次，if语句一直不成立，pos=j一直不执行，外循环第二轮就不执行了，所以最好时间复杂度是O(n)。最坏的情况是完全逆序，内循环的if语句一直成立，pos=j一直执行，外循环的执行次数是O(n)，内循环的执行次数是递减序列是O(n)，所以最坏时间复杂度是O(
)。平均情况下内循环执行的概率是一半，所以平均时间复杂度是O(
)。 　　空间复杂度： 双重循环，只定义了一个简单变量，所以空间复杂度是O(1)。 　　稳定性： 只有相邻的素才有可能交换，所以冒泡排序是稳定的。 　　递归性： 非递归。 　　原地性： 原地。 　　2.7 快速排序 　　快速排序是对冒泡排序的一种改进，是属于交换排序的一种，它的基本操作也是比较和交换，但是它比较的对象和交换的方式不同，冒泡排序是相邻的素比较并交换，快速排序是选择一个key，所有的数都和这个key比较，比它小的移动到它左边，比它大的移动到它右边。然后再对左边的区间和右边的区间重复进行这种操作，一直递归下去，直到区间只有一个素。所以递归完成并返回后，数组就排序好了。 　　算法描述： 选择一个素作为key，把所有小于这个key的都移动到左边，大于这个key的都移动到右边，这个key放在左区和右区的中间，这个操作叫做分割(partition)，然后分别对左区和右区递归这个操作。怎么选择这个key有很多种方法，本文中是直接取中间index的值作为key。 　　C语言实现： 　　代码分析： 先写个辅助函数swap用来交换素。do_quick_sort函数，输入参数是数组首地址、区间左index、区间右index，区间是左闭右闭区间。为什么函数的签名是这样的，和之前的排序算法的签名不太一样，之前参数都是arr和hr。这是因为快排是递归算法，所以它的参数要接收当前要处理的区间范围。do_quick_sort函数里面，首先要做的是递归结束检查，递归是什么时候结束呢，当区间只剩一个素或者是空区间的时候直接返回。继续走下去的话说明区间至少有两个素，可以做一轮分割。分割，我们选一个素作为key，这里有很多种选法，我们选择区间最中间的素作为key，也就是 (left+right)/2处的值，然后把这个key交换到区间的最左侧。然后我们以这个left处的值为key，对区间[left+1 – right]进行分割，使得最终这个区间以某个点为界，左部分的值都小于这个key，右部分都大于等于这个key。这是怎么做到的呢，这就是函数里面 for循环加 if 加 swap三个语句的神奇之处了。首先让index = left，[left+1 – index]代表的是左区，是小于key的值，[index+1 – i-1]代表的是右区，是大于等于key的值，[i – right]代表的是还未处理的区域，开始的时候，左区是空集，右区也是空集，未处理区是全集。每次循环的时候，i++，未处理区减少一个素，处理区增加一个素，增加的这个素是给左区还是右区呢，要判断它是否小于key，小于key的话，++index，左区增加一个素，右区由于i++了，所以右区的数量不变，swap交换的是待处理的位置i和之前右区的最左端，相当于是i增加了，右区先增加了一个素，如果它不比key小的，就什么也不操作，i就留作右区了，右区增加一个素，左区不变。如果它比key小的话，左区的最右端和最左端交换，index增加了1，把右区的一个位置划给了左区，右区相当于往右平移了一位。当循环完成之后，未处理区为空，整个区域分成了三个部分，left，[left+1 – index], [index+1, right], 左区都是小于key的，右区都是大于等于key的，然后再做一个swap(arr, left, index)操作，这样区域就变成了[left – index-1], index, [index+1, right], 很容易看出，左区都是小于key的，右区都是大于key，key自己在中间index的位置处，完美的完成了分割。下面就是递归调用了，分别对左区和右区进行递归调用。现在我们再来看一个问题，我们进来的时候整个区域的大小是大于等于2的，现在分割之后，左区或者右区有可能是空集的，所以left有可能大于index-1，index+1有可能大于right，所以函数开头处的>=检测是有必要的。为了让快排算法和其他算法的接口兼容，我们把具体做算法的函数叫做do_quick_sort，再向外提供一个接口quick_sort。 　　网上大部分的快排算法实现都是一个while循环内嵌两个并列的while循环，代码比较冗长。本文的快排实现是C语言之父Dennis Ritchie 在《The C Programming Language》书中所写的，代码非常简洁精巧，但是理解起来非常费劲。因此我们画个图来辅助理解：

　　算法总结： 递归算法都有分治合的特点，快排是先分后治没有和。分是把整个区间分成两个区间，一个区间都小于key，一个区间都大于等于key，这个是快排的重点和难点。治就是递归调用，递归调用在函数的尾部，所以是后递归算法。分的特点是先把key交换到最左边，然后进行分，最后再把key交换到临界点。 　　时间复杂度： 快排是递归算法，时间复杂度主要看递归树的深度，那么递归树深度是多少呢，如果不巧的话，每次分割的区间都是小于某个常量长度的区间和另一个区间的话，那么递归树的深度就是O(n)的，所以最坏时间复杂度是O(n2)，最好的情况是每次区间都是平分的，这样递归树的高度就是O(logn)的，所以最好时间复杂度是O(nlogn)。如果每次分割都是成比例的，就算是比例再小，达到1:9，甚至1:99，递归树的高度也是O(logn)的，所以平均时间复杂度是O(nlogn)。 　　空间复杂度： 在递归前定义了一个简单变量，递归后无变量定义，所以其空间复杂度就是递归树的高度，递归树高度最坏的情况是O(n)，最好的情况和平均情况是O(logn)，所以快排的空间复杂度最坏情况是O(n)，最好和平均是O(logn)，这是快排和其它排序算法一个显著的不同，其他排序算法的空间复杂度在所有的情况下都是一样的。 　　稳定性： 由于存在非相邻素交换的情况，所以快速排序是不稳定的。 　　递归性： 后递归，递归调用在函数的尾部叫后递归。 　　原地性： 原地。 　　2.8 归并排序 　　归并排序是先把最小的子序列给排好序，然后不断的合并子序列，最终达到排序的目的，归并排序是一种递归排序，采用的是分治合的思想，分是简单直接的分，直接平均分成两份，治是递归调用自己，合是把已经排序好的两个子序列合并成一个有序的序列。由于是递归调用在前，合在后，所以归并排序会先递归到最小的子序列，也就是一个素的序列，然后一个一个合成两个素的序列，两个双素的序列合并成一个四素序列，或者一个双素序列和一个单素序列合并成一个三素序列，就这样一直合并下去，直至底层函数返回，整个序列就排序好了。 　　算法描述： 先取序列的中点把序列分成两个区间，分别对左右两个区间进行递归调用，调用返回之后得到的是两个已排序的序列，然后把这两个序列合并成一个序列，合并采取的是非原地操作，把两个区间复制到一个临时数组中，然后左右两个区间依次选择最小的值复制回原区间中。由于是分成两个区间进行递归，所以这个算法实现是两路递归排序。 　　C语言实现： 　　代码分析： 入口先进行递归结束检测，当区间的长度小于等于1时结束递归直接返回，如果区间长度大于2，继续往下走。以中间index为分界把区间平分成两份，分别递归调用，调用返回后，得到的是两个已经排好序的序列，定义一个和区间总长度相同的临时数组，把整个区间都复制过去，然后同时遍历左区和右区，依次把更小的素复制回原区间，如果某个区间先复制完了，就把另一个区间的值直接复制完。代码使用了一定的编程技巧，使得代码非常精巧，但是不太好理解，但是逻辑是非常简单的，就是直接比较左区和右区的当前素哪个小，把小的复制回原数组，并把当前素index++。 　　算法总结：先递归调用，再进行整合。 　　时间复杂度：和快速排序的原理是一样的，时间复杂度的关键点在于递归树的深度，由于我们是按index分区的，所以总是能平分一个区，不存在分配不均匀的情况，所以递归树的深度总是O(logn)，所以最好最坏平均时间复杂度都是O(nlogn)。 　　空间复杂度：递归前定义了一个简单变量，其空间复杂度是O(logn)，递归后定义了和n相关的数组变量，其空间复杂度是O(n)，所以空间复杂度是O(n)。 　　稳定性：没有交换操作，合并时并不会改变素的相对位置，所以归并排序是稳定的。 　　递归性： 前递归，先进行递归，递归返回后再进行合并操作。 　　原地性： 非原地，定义了临时数组来存放被排序的值。 　　2.9 计数排序 　　计数排序是非比较排序中最简单的算法，它适用于范围比较集中的整数进行排序，我们第一章讲了非比较排序的基本原理，这里就不再赘述了。 　　算法描述： 先把原数组clone一份叫做arr2，再计算出数列中的最大值和最小值，创建一个长度为max-min+1的counts数组，先统计数列中每个整数出现的次数，然后累加计数数组，此时counts[i]代表在原数组中小于等于i的素的个数，然后逆序遍历arr2，把arr2按照正确的顺序放到原数列中。 　　C语言实现： 　　代码分析： 先遍历原数组，把原数组clone一份arr2，找到原数组的最大值和最小值，然后建立一个计数数组counts用来计数，长度是max-min+1，再遍历原数组，用素的值减去min作为下标在counts数组中寻址，对应的counts素++，代表这个数值的素的个数又增加了一个，遍历完成后，counts[i]代表在原数组中等于i的素的个数。再累加counts，累加完成后，counts[i]代表在原数组中小于等于i的素的个数。然后逆序遍历arr2，把arr2按照正确的顺序放到原数列中。为什么要逆序呢，这是因为counts[i]代表的是小于等于i的素的个数，逆序的话能让最后一个i值放到最后一个位置中去，这样就不会颠倒值相等的素的顺序，能保存排序的稳定性。 　　算法总结：先遍历原数组，找到最大值最小值，再遍历原数组，统计各个数值出现的次数，再累加计数数组，再逆序遍历arr2数组回写到原数组。 　　时间复杂度：遍历3次原数组，遍历2次计数数组，原数组的长度是n，计数数组的长度是k，k = max-min+1，是一个与n无关的数，所以时间复杂度是O(n+k)，不存在什么特殊情况，所以最好最坏平均时间复杂度都O(n+k)。 　　空间复杂度：定义了一个计数数组，长度是k，k = max-min+1，是一个与n无关的数，clone了原数组，长度是n，所以空间复杂度是O(n+k)。 　　稳定性：计数排序是稳定的，代码分析中讲了保持排序稳定的原因。 　　递归性： 非递归。 　　原地性： 非原地。 　　2.10 桶排序 　　桶排序是也是一种非比较排序，它比较适合那些数据分布比较均匀的数据，其基本思想是根据数据的范围，把其分为N个桶，然后把所有数据放入相应的桶中，每个桶内再进行排序，然后把所有的桶按顺序收回数据，整个数据就排序好了。 　　算法描述： 把数据分到N个桶中，每个桶中再进行排序。 　　C语言实现： 　　暂无 　　代码分析： 暂无。 　　算法总结： 暂无 　　时间复杂度： 最好最坏平均时间复杂度都是O(n+k)。 　　空间复杂度： 空间复杂度是O(n+k)。 　　稳定性： 桶排序是稳定的。 　　递归性： 非递归。 　　原地性： 非原地。 　　2.11 基数排序 　　基数排序也是一种非比较排序，它只适用于对非负整数进行排序，它的基本原理是先对个位进行排序，再对十位进行排序，再对百位进行排序，……，直至最高位，对每位进行排序的方法一定要选择稳定排序，比如计数排序。基数排序不一定要把整数看成是10进制的，可以把它当成任意进制的数来处理都行。 　　算法描述： 从最低位开始进行稳定排序，……，直至最高位。 　　C语言实现： 　　代码分析： 先计算数列中的最大值，再计算出它的位数，本代码是按照16进制来看待的，这样方便运算。然后从低位到高位依次遍历，每次遍历都采取计数排序，这个计数排序它的n还是外部的n，但是它的k是常量16，因为它是按16进制来处理的，一位16进制数最大的值是15，最小是0。计数排序的逻辑我们就不再赘述了。 　　算法总结：外层循环按照从低位到高位的顺序进行循环，内层是计数排序。 　　时间复杂度：外层循环的次数是位数k，内层循环是计数排序，由于此时计数排序的k是常量，所以内层循环的复杂度是O(n)，由于不存在特殊情况，所以最好最坏平均时间复杂度都是O(nk)。 　　空间复杂度： 内循环的空间复杂度是O(n)，外循环不会累积内循环的存储空间，所以空间复杂度是O(n)。 　　稳定性： 每轮排序都是用的稳定排序，所以最终排序也是稳定的，所以基数排序是稳定的。 　　递归性： 非递归。 　　原地性： 非原地。 　　三、总结回顾 　　至此，我们已经全面详细讲解了所有常见的排序算法，包括算法的原理、实现方法、以及各种性质的分析(桶排序除外)。下面我们先画个图回顾一下。

　　我们从上到下、从左到右再把这个图看一遍，仔细回忆一下各个算法的基本原理、实现方法、和对它各种性质的分析。从左到右，排序算法先根据是否使用比较分为比较排序和非比较排序，比较排序根据其基本原理的不同分为选择排序、插入排序、交换排序、归并排序。归并排序是递归排序，其时间复杂度是O(nlogn)，已经非常优秀了，没有改进空间了，而选择排序、插入排序、交换排序的时间复杂度都是O(n2)，还有改进空间，于是分别改进出了堆排序、希尔排序、快速排序。非比较排序中最简单最直接的是计数排序，它为了处理数列中有重有漏的问题而采取计数方法。桶排序是对分布均匀的数据分桶进行排序。基数排序是一种比较巧妙的排序，一般人都想不到还能这样排序。 　　图中没有写它们的适用性，我们在这里说一下。比较排序的适用性非常强，可适用于任何数据。非比较排序的适用性比较窄，计数排序适用于对范围比较集中的整数进行排序，桶排序适用于分布比较均匀的数据，基数排序适用于正整数。 　　我们再来看一看递归性、原地性与稳定性和空间复杂度之间的关系。可以看出非原地排序都是稳定排序，原地排序由于需要交换，所以相邻交换的都是稳定排序，不相邻交换的都是不稳定排序。非递归原地排序的空间复杂度都是O(1)，非递归非原地排序的空间复杂度都是线性的。递归排序的空间复杂度至少是O(logn)，因为原地排序不需要额外分配空间，所以递归原地排序的空间复杂度是O(logn)，而非原地排序的空间复杂度是O(n)，所以非递归非原地排序的空间复杂度是O(n)。 　　再来看时间复杂度，非比较排序中的计数排序和桶排序的平均时间复杂度都是O(n+k)，是线性的，计数排序中，如果把位数k看成是不大于15的常量，计数排序的平均时间复杂度也可以看成是线性的。比较排序中，所有的简单排序的平均时间复杂度都是O(n2)，而复杂排序基本都是O(nlogn)，除了希尔是O(n1.3)。选择排序和归并的时间复杂度不存在优化和恶化的情况。插入排序和冒泡排序存在优化的情况，当数列已经排好序时，其时间复杂度优化为O(n)。快排的时间复杂度存在恶化的情况，当区间分割总是极度不均匀时，其时间复杂度恶化为O(n2)。 　　所有算法中，逻辑上最难理解的是堆排序和基数排序，代码上最难理解的是快速排序。一般情况下运行效率最高的是快排，所以快排才叫快排，很多库的排序算法的默认实现就是快排。 　　参考文献： 　　《Introduction to Algorithms》 　　《Algorithms》 　　《Algorithms in a Nutshell》 　　《An Introduction to the Analysis of Algorithms》 　　文中的代码放到github上了，大家可以参考一下 　　https://github.com/orangeboyye/sort 　　原文链接：深入理解排序算法_城中之城的博客-CSDN博客