本章用C语言实现每个排序算法，一个算法一个小节，每个小节的内容依次是算法简介、算法描述、C语言实现、代码分析、算法总结、时间复杂度、空间复杂度、稳定性、递归性、原地性。

2.1 如何分析排序算法

如何计算一个算法的时间复杂度和空间复杂度呢，这里面有严谨的数学和严密的逻辑，想要学习的同学可以去研究相关的专业书籍，本文会使用比较直观好理解的，但是不太严谨的方法进行分析。

我们先说时间复杂度，对于大部分算法来说，一般都是内外双重循环结构，外循环的复杂度一般都是O(n)，内循环复杂度和外循环复杂度的乘积就是整个算法的复杂度。内循环复杂度有几种情况，如果内循环复杂度每轮都是个固定值，那就很简单，比如内循环总是循环n次，那么内循环复杂度就是O(n)，算法的复杂度就是O(n²)。如果内循环的复杂度是O(logn)，那么算法的复杂度就是O(nlogn)。但是很多时候内循环的执行次数往往是变化的，有的是递增序列从1到n，有的是递减序列从n到1，此时我们可以算一下内循环的平均执行次数，(n+1)*n/2/n = 0.5n+0.5，忽略常量和系数，内循环的复杂度就是O(n)，此时算法的复杂度就是O(n²)，这种情况比较常见。还有一些特殊情况，对于有些特殊数列，内循环的条件执行一次就结束了，内循环的复杂度就是O(1)，所以算法的复杂度是O(n)。还有一种情况是内循环第一轮执行了n次，外循环一次就结束了，此时算法复杂度也是O(n)。

对于递归算法来说，要看它的递归树层数和每层的时间复杂度，我们画个图看一下。

我们可以看到每一层的数据规模之和都是n，而树的高度一般是logn，所以递归算法的时间复杂度一般都是O(nlogn)，只要树别退化成线性结构。如果退化了，树的高度就是n，那么算法复杂度就变成了O(n²)了。

我们再来看空间复杂度，如果我们分配的变量是简单变量，与输入规模n无关，那么这个变量本身的空间复杂度就是O(1)，如果它分配在外层循环里，它的复杂度并不会乘以n，因为循环的每一轮它都销毁重建了，它并不会累积。如果它出现在内循环里，它的复杂度既不会乘以n，更不会乘以n²，这点可能难以理解。我们先只看内循环，和刚才讲的道理一样，它一直在销毁重建，所以复杂度还是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语言实现：

void select_sort(int arr[], int nr){ for(int i = 0; i < nr-1; i++){ int min= i; for(int j = i+1; j < nr; j++){ if(arr[min] > arr[j]) min= j; } int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; }}

代码分析： 通过双重循环，外循环从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(n²)，内外循环的执行都是必然的，不存在特例，所以最好最坏平均时间复杂度都是O(n²)。

空间复杂度： 双重循环，只定义了一个简单变量，所以空间复杂度是O(1)。

稳定性： 每次交换元素时都很大可能交换的是不相邻元素，所以简单选择排序是不稳定的。

递归性： 非递归。

2.3 堆排序

堆排序是利用堆这种数据结构进行排序的一种算法。堆是一个近似完全二叉树，并且对于大顶堆来说每个子节点的值都小于等于它的父节点，对于小顶堆来说每个子节点的值都大于等于它的父节点。堆排序是对简单选择排序的一种优化，简单选择排序的问题在于它的比较次数太多，因为它每次比较完一遍之后只留下了最小值下标信息，其他比较信息都丢了，导致比较次数是O(n²)。堆排序利用堆的数据结构，每次选择出来一个最大值之后，之前的很多比较数据还保留在堆结构中，从而减少了比较次数。堆排序的总体逻辑和简单选择排序差不多，我们以大顶堆升序排序为例说明，先把数组建立为大顶堆，然后把堆顶也就是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语言实现：

static void heap_adjust(int arr[], int length, int node){ int key = arr[node]; while(1){ int child = node*2 + 1; if(child >= length) break;  if(child+1 < length && arr[child+1] > arr[child]) child++; if(arr[child] <= key) break;  arr[node] = arr[child]; node = child;  } arr[node] = key;} void heap_sort(int arr[], int nr){ for(int node = nr/2 - 1; node >= 0; node--) heap_adjust(arr, nr, node);  for(int length = nr-1; length > 0; length--){ int tmp = arr[0]; arr[0] = arr[length]; arr[length] = tmp; heap_adjust(arr, length, 0); } }

代码分析： 首先有个辅助函数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语言实现：

void insert_sort(int arr[], int nr){ for(int i = 1; i < nr; i++){ int j, key = arr[i]; for(j = i; j > 0 && arr[j-1] > key; j--) arr[j] = arr[j-1]; arr[j] = key; }}

代码分析： 外层循环表达的是未排序区，index从1开始，到nr-1结束，初始排序区是[0 – 0]，就一个元素，肯定是已排序的。取未排序区的第一个数作为待插入数，保存在局部变量key中，未排序的首位空间转换为已排序区的空间，根据key扫描已排序空间，比key大的都右移一位，直到遇到不比key大的数值为止。内循环结束后，j的值就是key要插入的位置，这个位置之前的值都小于等于key，之后的位置都大于key。执行arr[j] = key，完成插入。外循环结束后，未排序区为空，排序成功。

算法总结： 双重循环，背道而行，数据不断右移为key腾挪位置，直到找到key应该在的位置，最后插入。

时间复杂度： 外循环复杂度是O(n)，内循环的执行次数是有条件的，假设条件总成立，也就是数列是逆序的情况，内循环的复杂度是O(n)，所以最坏时间复杂度都是O(n²)。假设内循环的条件总是不成立，也就是数列已排序的情况，内循环的复杂度是O(1)，所以最好时间复杂度都是O(n)。平均情况也就是一般情况，内循环里面的操作有一半的概率会执行，也就是最坏情况的一半，所以平均时间复杂度还是O(n²)。

空间复杂度： 双重循环，定义了两个简单变量，所以空间复杂度是O(1)。

稳定性： 逻辑上可以看成是key不断地和前面的元素进行交换，也是属于只交换相邻元素，所以简单插入排序是稳定的。

递归性： 非递归。

原地性： 原地。

简单插入排序和简单选择排序对比一下，最好时间复杂度，前者是O(n)，后者是O(n²)，平均时间复杂度虽然都是O(n²)，但是前者的系数是1/4，后者的系数是1/2，稳定性，前者稳定，后者不稳定，所以简单插入排序完胜简单选择排序。

2.5 希尔排序

希尔排序是对简单插入排序的一种改进，又叫做缩小增量排序，也叫分组插入排序。它对插入排序的改进是基于插入排序的两个特点，1是插入排序对于越接近排好序的数列效率越高，2是插入排序一般情况下是低效的，因为内循环一次只能把数据移动一位。针对插入排序的特点和缺点，我们可以这样改进它。对数列进行分组插入排序，比如先分5组分别进行插入排序，再分3组分别进行插入排序，再分1组也就是不分组进行插入排序。也就是说希尔排序最后要进行一次插入排序，你也许会觉得之前就进行了很多次操作，最后还要进行一次插入排序，效率肯定比插入排序差。但是这是不对的，因为插入排序的效率受它的输入数据的有序性影响很大，如果输入数据是已经排序的，那么插入排序的效率就是O(n)，输入数据越接近已排序，插入排序的效率就越接近O(n)。前面的分组插入排序就是为了使整个数组更接近排序状态。它是第一个突破O(n²)的算法。

算法描述： 增量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语言实现：

void shell_sort(int arr[], int nr){ for(int d = nr/2; d > 0; d /= 2){ d |= 1; for(int i = d; i < nr; i++){ int j, key = arr[i]; for(j = i; j >=d && arr[j-d] > key; j -= d) arr[j] = arr[j-d]; arr[j] = key; } }}

代码分析： 三重循环，最外层循环，是d增量循环，从nr/2开始，每次减半，到1停止。内层两层for循环是标准的简单插入排序算法，加入了分组考虑。

算法总结： 三重循环，外层循环是d增量每次减半，内两层循环是简单插入排序。

时间复杂度： 希尔排序的时间复杂度是和增量序列有着密切的关系的，最好时间复杂度可以达到O(n)，最坏时间复杂度可以到O(n2)，如果按照Sedgewick提出的增量序列，最坏时间复杂度和平均时间复杂度可以达到O(n^1.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语言实现：

void bubble_sort(int arr[], int nr){ for(int i = 0; i < nr-1;){ int pos = nr-1; for(int j = nr-1; j > i; j--){ if(arr[j] < arr[j-1]){ int tmp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = tmp; pos = j; } } i = pos; }}

代码分析： 双重循环，外层循环控制每次冒泡的顶端，从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(n²)。平均情况下内循环执行的概率是一半，所以平均时间复杂度是O(n²)。

空间复杂度： 双重循环，只定义了一个简单变量，所以空间复杂度是O(1)。

稳定性： 只有相邻的元素才有可能交换，所以冒泡排序是稳定的。

递归性： 非递归。

2.7 快速排序

快速排序是对冒泡排序的一种改进，是属于交换排序的一种，它的基本操作也是比较和交换，但是它比较的对象和交换的方式不同，冒泡排序是相邻的元素比较并交换，快速排序是选择一个key，所有的数都和这个key比较，比它小的移动到它左边，比它大的移动到它右边。然后再对左边的区间和右边的区间重复进行这种操作，一直递归下去，直到区间只有一个元素。所以递归完成并返回后，数组就排序好了。

算法描述： 选择一个元素作为key，把所有小于这个key的都移动到左边，大于这个key的都移动到右边，这个key放在左区和右区的中间，这个操作叫做分割(partition)，然后分别对左区和右区递归这个操作。怎么选择这个key有很多种方法，本文中是直接取中间index的值作为key。

C语言实现：

static void swap(int arr[], int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;} static void do_quick_sort(int arr[], int left, int right){ if(left >= right) return;  swap(arr, left, (left+right)/2); int index = left; for(int i = left+1; i <= right; i++) if(arr[i] < arr[left]) swap(arr, ++index, i); swap(arr, left, index);  do_quick_sort(arr, left, index-1); do_quick_sort(arr, index+1, right);} void quick_sort(int arr[], int nr){ do_quick_sort(arr, 0, nr-1);}

代码分析： 先写个辅助函数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(n²)，最好的情况是每次区间都是平分的，这样递归树的高度就是O(logn)的，所以最好时间复杂度是O(nlogn)。如果每次分割都是成比例的，就算是比例再小，达到1:9，甚至1:99，递归树的高度也是O(logn)的，所以平均时间复杂度是O(nlogn)。

空间复杂度： 在递归前定义了一个简单变量，递归后无变量定义，所以其空间复杂度就是递归树的高度，递归树高度最坏的情况是O(n)，最好的情况和平均情况是O(logn)，所以快排的空间复杂度最坏情况是O(n)，最好和平均是O(logn)，这是快排和其它排序算法一个显著的不同，其他排序算法的空间复杂度在所有的情况下都是一样的。

稳定性： 由于存在非相邻元素交换的情况，所以快速排序是不稳定的。

递归性： 后递归，递归调用在函数的尾部叫后递归。

2.8 归并排序

归并排序是先把最小的子序列给排好序，然后不断的合并子序列，最终达到排序的目的，归并排序是一种递归排序，采用的是分治合的思想，分是简单直接的分，直接平均分成两份，治是递归调用自己，合是把已经排序好的两个子序列合并成一个有序的序列。由于是递归调用在前，合在后，所以归并排序会先递归到最小的子序列，也就是一个元素的序列，然后一个一个合成两个元素的序列，两个双元素的序列合并成一个四元素序列，或者一个双元素序列和一个单元素序列合并成一个三元素序列，就这样一直合并下去，直至底层函数返回，整个序列就排序好了。

算法描述： 先取序列的中点把序列分成两个区间，分别对左右两个区间进行递归调用，调用返回之后得到的是两个已排序的序列，然后把这两个序列合并成一个序列，合并采取的是非原地操作，把两个区间复制到一个临时数组中，然后左右两个区间依次选择最小的值复制回原区间中。由于是分成两个区间进行递归，所以这个算法实现是两路递归排序。

C语言实现：

static void do_merge_sort(int arr[], int left, int right){ if(left >= right) return; int mid = (left+right)/2; do_merge_sort(arr, left, mid); do_merge_sort(arr, mid+1, right);  int count = right - left + 1; int tmp[count]; for(int i = 0; i < count; i++) tmp[i] = arr[left+i];  int j = 0, jmax = mid-left+1; int k = jmax, kmax = count; for(int i = left; i <= right; i++) arr[i] = j >= jmax || (k < kmax && tmp[k] < tmp[j]) ? tmp[k++] : tmp[j++];} void merge_sort(int arr[], int nr){ do_merge_sort(arr, 0, nr-1);}

代码分析： 入口先进行递归结束检测，当区间的长度小于等于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语言实现：

void count_sort(int arr[], int nr){ int arr2[nr]; int max = arr[0]; int min = arr[0]; for(int i = 0; i < nr; i++){ arr2[i] = arr[i]; if(max < arr[i]) max = arr[i]; if(min > arr[i]) min = arr[i]; }  int length = max - min + 1; int counts[length]; for(int i = 0; i < length; i++) counts[i] = 0;  for(int i = 0; i < nr; i++) counts[arr2[i] - min]++;  for(int i = 1; i < length; i++) counts[i] += counts[i-1];  for(int i = nr-1; i >= 0; i--) arr[--counts[arr2[i]-min]] = arr2[i];}

代码分析： 先遍历原数组，把原数组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语言实现：

void radix_sort(int arr[], int nr){ int max = arr[0]; for(int i = 1; i < nr; i++) if(max < arr[i]) max = arr[i];  int d = 1; while((max = max >> 4) != 0 ) d++;  for(int k = 0; k < d; k++){ int arr2[nr]; for(int i = 0; i < nr; i++) arr2[i] = arr[i];  int length = 1 << 4; int counts[length]; for(int i = 0; i < length; i++) counts[i] = 0;  for(int i = 0; i < nr; i++) counts[(arr2[i] >> 4*k) & 0x0F]++;  for(int i = 1; i < length; i++) counts[i] += counts[i-1];  for(int i = nr-1; i >= 0; i--) arr[--counts[(arr2[i] >> 4*k) & 0x0F]] = arr2[i]; }}

代码分析： 先计算数列中的最大值，再计算出它的位数，本代码是按照16进制来看待的，这样方便运算。然后从低位到高位依次遍历，每次遍历都采取计数排序，这个计数排序它的n还是外部的n，但是它的k是常量16，因为它是按16进制来处理的，一位16进制数最大的值是15，最小是0。计数排序的逻辑我们就不再赘述了。

算法总结： 外层循环按照从低位到高位的顺序进行循环，内层是计数排序。

时间复杂度： 外层循环的次数是位数k，内层循环是计数排序，由于此时计数排序的k是常量，所以内层循环的复杂度是O(n)，由于不存在特殊情况，所以最好最坏平均时间复杂度都是O(nk)。

空间复杂度： 内循环的空间复杂度是O(n)，外循环不会累积内循环的存储空间，所以空间复杂度是O(n)。

稳定性： 每轮排序都是用的稳定排序，所以最终排序也是稳定的，所以基数排序是稳定的。

递归性： 非递归。

三、总结回顾