前言本文将补充剩下的常见排序算法并对这些排序算法进行个大概的总结主要是介绍递归类的算法花费的篇幅比较多快速排序、归并排序还会尝试把递归的形式改为非递归并补充一些关于排序的小概念1.交换类排序1.1冒泡排序冒泡排序这个算法应该是我们大多数人学到的第一个算法因为这个算法足够的简单在我之前的博客里也介绍过但为了完整性我还是把它给加上了。冒泡排序之所以叫冒泡排序是因为它的排序过程就像一个个气泡浮出水面一样把这个待排序的元素依次向右比较经过一趟之后最大或者最小我们这里都以升序为例子的元素就出现在末尾了如果有N个元素的话假如最坏的情况下我们要把逆序的数组排成升序那么分别要走 N * N - 1* N - 2。。。 这样的话根据数列求和公式我们可以认为这个排序的算法为 ON ^ 2的时间复杂度。但是不可能原数列都是最坏的情况 因此我们可以进行一个优化观察发现当一趟里数与数不在交换时这个数组就已经有序了这样我们就不必非要完全的走完一个完整的冒泡排序了。//冒泡排序 void BubbleSort(SortDataType* a, int n) { for (int i 1; i n; i) { bool flag true;//小小优化点 for (int j 0; j n - i; j) { if (a[j] a[j 1]) { Sawp(a[j], a[j 1]); flag false; } } if (flag) { break;//不交换就有序了就退出 } } }但即便加上这个小优化这个排序的时间复杂度还是很高我这里就不测试它的速度了因为这个算法比起我们接下来要介绍的快速排序在速度上的差距可以说是天差地别1.2快速排序终于到了我们这篇文章的重量级内容这个快速排序有很多的版本但主要都体现在一趟遍历方式的不同上核心思想都是一样的我这里都会依次介绍各个版本还会介绍如何把递归的写法改成非递归的方法建议先去看看我之前写的这篇【数据结构】二叉树相关经典函数C语言实现理解起来会更加的容易和自然下面是我们要实现的各个版本的快速排序//快速排序 //快速排序hoare版本 void QuickSortHoare(SortDataType* a, int left, int right); //快速排序挖坑法 void QuickSortHole(SortDataType* a, int left, int right); //快速排序前后指针法 void QuickSortPtr(SortDataType* a, int left, int right); //快速排序非递归法 void QuickSortNoR(SortDataType* a, int left, int right);1.2.1快速排序hoare版本快速排序这个算法就是由Tony Hoare已遗憾离世这位大佬提出来的可以说是最经典的版本其实后面各种版本都只是在遍历方式有所不同但都需要遍历一遍所以其实并没有时间复杂度的优劣之分只是有些遍历方式可以更方便直观的控制划分递归区间的keyi这个算法是怎么让数列有序的我们可以先从它遍历一遍一开始的数组开始分析假如我们要排序的数数组为此时我们对定义两个左右指针指向的是当前位置的下标分别从左右区间开始我们还需要指定一个数为key这里的话我就使用指向key这个数的下标keyi直接使用key也是可以的这里有个小细节如何你以左边作为keyi的话需要让右边先走这样才能保证begin与end相遇的位置一定是小于a[keyi]的置于为什么后面我们会有证明回到这个过程中我们会让end先向左走end的目的是为了找到比a[keyi]小的数字因为我们要排的是升序当走到比a[keyi]小的数字就停下来同理begin也是一样的道理begin从左往右找到比a[keyi]大的数字当走到这个数字时就停下来接着让begin和end指向的数字做一下交换。重复这个过程最后当begin和end相遇时相遇左边的数字都是小于等于a[keyi]的而右边的数字都是大于等于a[keyi]的当左右指针相遇时接着让a[keyi]与a[begin]交换让keyi begin(这是为了后面划分递归的区间)这个时候我们就完成了原数组里数字3的排序我们来看看这整个过程的动图演示为了完成其他元素的排序我们可以通过递归来实现其他元素的排序。当keyi begin 时我们会划分两个区间 [left, keyi - 1] [keyi] [keyi 1, right]接着按有点像二叉树的前序遍历的顺序来分别递归这些子区间下面是代码实现// 快速排序hoare版本 void QuickSortHoare(SortDataType* a, int left, int right) { if (left right) return; int begin left, end right; int keyi left; while (begin end) { while (begin end a[end] a[keyi]) { --end; } while (begin end a[begin] a[keyi]) { begin; } Sawp(a[end], a[begin]); } Sawp(a[keyi], a[begin]); keyi begin; QuickSortHoare(a, left, keyi - 1); QuickSortHoare(a, keyi 1, right); }这段代码其实是可以进行优化的但这个我们后面再说这里我们先解决之前的疑问为什么要先移动另一边而且为什么这样就可以保证相遇的值是一定小于a[keyi]的这里我就以上面的代码作为例子来说明首先begin和end指针相遇有两种情况,都是end先走的情况下1end 遇到begin : end先走end找比key小的值没找到小的值直接遇到了begin而在此时begin所停留的位置是上一次交换的值这样现在begin所指向的值肯定是小于key的2begin遇到end end先走 begin没有遇到比key大的值直接遇到了end此时end所在所停留的地方是比key小的值因为end就是因为遇到比key小的值而停下来的所以就可以证明相遇的地方值是肯定小于a[keyi]的,可以看到还是挺隐蔽的后面的各种快速排序版本基本上就是针对这种情况的优化但因为都要遍历数组一遍所以在时间的复杂度上是一样的要实现那种看你自己的喜好快速排序的优化当我们要排序的原数列存在大量的重复元素时或者是数列原本就是有序时我们大概率会取到极端值这样就会有一边的递归深度过深而一边可能只递归几层形成一个失衡的状态这是一个比较极端的情况这样的话每次遍历只会让一个元素有序从左到右有N个元素的话这个算法就是变成 ON ^ 2的时间复杂度这是我们不能接受的当然这种情况出现的概率很小但我们可以针对这种情况优化我们的快速排序。我们可以采取一个叫做三数取中的方法来优化这种情况三数取中就是我们在指定keyi时我们可以写一个函数让他选出原数列中不极端的数值让是需要注意的是我们的keyi还是left的位置所以我们选出来之后还需要通过Swap来交换一下。函数实现及其三数取中优化//三数取中 int Getmid(SortDataType* a, int left, int right) { int mid (left right) / 2; if (a[left] a[mid]) { if (a[mid] a[right]) return mid; else if (a[left] a[right]) return right; else return left; } else //a[left] a[mid] { if (a[mid] a[right]) return mid; else if (a[left] a[right]) return left; else return right; } } // 快速排序hoare版本 void QuickSortHoare(SortDataType* a, int left, int right) { if (left right) return; int begin left, end right; int keyi Getmid(a, left, right); Sawp(a[keyi], a[left]); keyi left; while (begin end) { while (begin end a[end] a[keyi]) { --end; } while (begin end a[begin] a[keyi]) { begin; } Sawp(a[end], a[begin]); } Sawp(a[keyi], a[begin]); keyi begin; QuickSortHoare(a, left, keyi - 1); QuickSortHoare(a, keyi 1, right); }除了三数取中还有一个可以优化快速的方法叫做小区间优化我们观察我们的快速排序代码是不是递归的过程很想一个二叉树只不过结点变成了区间所以这里我简单画一个不严谨的草图可以看到随着递归层数的增加分裂的区间也越来越多最后一层的小区间基本占了总递归区间的大半但有一个特性我们发现当随着递归层数的增加区间是越来越小的那它相比于递归层数少的较大区间是不是就相对的有序比较数据量比较小处理比较有序的数列用什么排序算法比较好呢那当然我们的插入排序这里就没必要使用希尔排序了关于这两个排序在我之前的文章里我就直接用了。小区间优化// 快速排序hoare版本 void QuickSortHoare(SortDataType* a, int left, int right) { if (left right) return; //小区间优化 if (right - left 1 10) { InsertSort(a left, right - left 1); return; } int begin left, end right; int keyi Getmid(a, left, right); Sawp(a[keyi], a[left]); keyi left; while (begin end) { while (begin end a[end] a[keyi]) { --end; } while (begin end a[begin] a[keyi]) { begin; } Sawp(a[end], a[begin]); } Sawp(a[keyi], a[begin]); keyi begin; QuickSortHoare(a, left, keyi - 1); QuickSortHoare(a, keyi 1, right); }其实就算是不加上这两个优化在大多数情况下都没啥问题感兴趣可以自己用我上篇文章写的函数来测试一下优化效果你会发现其实都是大差不差的时间复杂度分析我们发现当数列有n个元素时我们会向下递归long n层栈帧空间会复用所以不是2 * long层每层都会遍历一遍区间。总的元素有N个所以N个元素总共遍历N次所以是ON所以总的平均时间复杂度为ON * long N是一个很优秀的算法1.2.2快速排序挖坑法其实快速排序的大部分内存和核心思想都在上面介绍完了下面的各种版本只是遍历区间的方式不同罢了这里我就简单快速的介绍一下这里我们先看动图演示的遍历方式左右指针依旧是找大找小只不过停下的位置会变成一个坑位当另外一个指针停下时那个地方会变成新的坑位然后把原来值填入之前的坑位中这样相遇的地方就肯定是一个坑位了// 快速排序挖坑法 void QuickSortHole(SortDataType* a, int left, int right) { if (left right) return; if (right - left 1 10) { InsertSort(a left, right - left 1); return; } int begin left, end right; int mid Getmid(a, left, right); Sawp(a[mid], a[left]); int key a[left]; int hole left;//初始的坑位 while (begin end) { while (begin end a[end] key) { end--; } //更新坑位 a[hole] a[end]; hole end; //更新坑位 while (begin end a[begin] key) { begin; } a[hole] a[begin]; hole begin; } a[hole] key; QuickSortHole(a, left, hole - 1); QuickSortHole(a, hole 1, right); }坑位法我个人认为让交换的过程更加的直观了1.2.3快速排序前后指针法前后指针法的遍历逻辑其实和上面的区别挺大的如果你有刷过双指针的题的话相信理解起来还是比较的容易的我们这里先看动图演示后指针cur在前面找的比key小的值如何找到了就让pre指针后移一位让后把小的值换到pre的位置这样当cur越界循环结束时pre就是key要交换的地方。其实前后指针法代码写起来还是很容易的//快速排序前后指针法 void QuickSortPtr(SortDataType* a, int left, int right) { if (left right) return; if (right - left 1 10) { InsertSort(a left, right - left 1); return; } int mid Getmid(a, left, right); Sawp(a[mid], a[left]); int key a[left]; int pre left; int cur pre 1; while (cur right) { if (a[cur] key pre ! cur) { Sawp(a[cur], a[pre]); } cur; } Sawp(a[pre], a[left]); QuickSortPtr(a, left, pre - 1); QuickSortPtr(a, pre 1, right); }1.2.4快速排序的非递归法当递归深度过深时就会有栈溢出的风险因为建立新的栈帧是在栈区开辟的而栈区的内存大小相比于堆区就小得多。所以为了避免这个风险有时候我们需要把递归改成非递归的写法因为我们动态申请的数组等等都是在堆区申请的。那我们如何改成非递归的写法呢这里就需要借助一个数据结构---栈。因为C语言不想C一样有STL中的stack可以用所以这里我就用我之前写过的一个栈感兴趣可以看我之前的文章【数据结构】栈及其C语言模拟实现我们找到栈是一个后进先出的结构因此利用这个特性来模拟递归这个栈就会以前序遍历的方式来处理这个数列。其实用层序遍历BFS的方法也是可以的但是为了和前面递归的逻辑保持一致这里就使用栈来模拟这个过程如果层序遍历的话可以用我们的队列来实现我这里就不另外介绍了另外我们没必要另外在栈那里封装一个结构体来存放左右区间我们只需要每次存取都执行两次就可以了下面是具体的代码实现//快速排序非递归法 void QuickSortNoR(SortDataType* a, int left, int right) { ST mp; STInit(mp); STPush(mp, right); STPush(mp, left); while (!STEmpty(mp)) { int L STTop(mp); STPop(mp); int R STTop(mp); STPop(mp); int mid Getmid(a, L, R); Sawp(a[mid], a[L]); int begin L, end R; int keyi L; while (begin end) { while (begin end a[end] a[keyi]) { --end; } while (begin end a[begin] a[keyi]) { begin; } Sawp(a[end], a[begin]); } Sawp(a[keyi], a[begin]); keyi begin; if (keyi 1 R) { STPush(mp, R); STPush(mp, keyi 1); } if (L keyi - 1) { STPush(mp, keyi - 1); STPush(mp, L); } } STDestroy(mp); }2.归并排序与计数排序2.1归并排序归并排序也是通过递归来实现的一种排序算法与快速排序不同的是归并排序对空间的消耗比较。因为递归算法的核心思想就是把区间一分为二层层递归到后面当左右两个区间都只有一个元素时这个区间可以看成是以及有序了于是我们就开始返回这时我们会把两个小区间向上归并为一个较大的区间这时我们会让按从小到大的顺序的把两个小区间的元素放在大区间里这样就可以保证向上的过程中数组在向上的过程中逐渐的有序下面是总的概括图我们来看看动图演示当有N个元素时会向下递归 long N 层归并N次所以归并排序时间复杂度为O (N * long N)另外另外开辟一个N个大小的空间用于辅助归并所以空间复杂度为ON下面我们来进行代码的实现void _MergeSort(SortDataType* a, SortDataType* tmp, int left, int right) { if (left right) return; int mid (left right) / 2; _MergeSort(a, tmp, left, mid); _MergeSort(a, tmp, mid 1, right); int begin1 left, end1 mid; int begin2 mid 1, end2 right; int i begin1; while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[i] a[begin1]; } else { tmp[i] a[begin2]; } } while (begin1 end1) { tmp[i] a[begin1]; } while (begin2 end2) { tmp[i] a[begin2]; } memcpy(a left, tmp left, sizeof(SortDataType) * (right - left 1)); } //归并排序 void MergeSort(SortDataType* a, int n) { SortDataType* tmp (SortDataType*)malloc(sizeof(SortDataType) * n); if (tmp NULL) { perror(malloc fail!); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp NULL; }归并排序的非递归实现先别管这么模拟出递归的过程我们先来解决一个问题那就是我们还能通过简单的除2划分区间吗那当然是不行的因为循环的进行有时候区间就会变得不合法在递归版本中我们通过设置递归出口解决了这个问题但在迭代中我们有可能存在越界的问题此时区间不合法时我们进行归并就会发生错误。因此我们还需要在拷贝时对边界进行修正。接着我们该如何通过递归呢还记得我们之前学习过的希尔排序吗这里就用到了一点希尔排序的思想只不过与希尔排序不同的是这个gap是逐渐向外扩张的。我们可以首先定义一个gap从1开始因为分别对数组进行 11归并 22归并 44归并。。。。 下面是代码实现//归并排序非递归版 void MergeSortNoR(SortDataType* a, int n) { SortDataType* tmp (SortDataType*)malloc(sizeof(SortDataType) * n); if (tmp NULL) { perror(malloc fail!); return; } int gap 1; while (gap n) { for (int i 0; i n; i 2 * gap) { int begin1 i, end1 i gap - 1; int begin2 i gap, end2 i 2 * gap - 1; int j i; //修正区间 if (begin2 n) break; if (end2 n) end2 n - 1; while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[j] a[begin1]; } else { tmp[j] a[begin2]; } } while (begin1 end1) { tmp[j] a[begin1]; } while (begin2 end2) { tmp[j] a[begin2]; } memcpy(a i, tmp i, sizeof(SortDataType) * (end2 - i 1)); } gap * 2; } free(tmp); tmp NULL; }2.2计数排序计数排序是一个比较特殊的排序算法它是具有一定的局限性不能排浮点数但在某下场景下这个排序算法可以达到ON的时间复杂度非常的快计数排序会另外开辟一个新数组用来记录原数组里各个元素出现的次数这样当我们通过下标映射循环一遍原数组时原数组里各个元素出现的次数就被我们辅助数组count存下来了这时我们再从count下标从小到大依次把小标就是数组里面的值拷贝会原数组可以数组就天然的有序了可以说是一个很巧妙的算法很容易想到的是万一原数列里有元素的大小很大怎么办?万一里面有负数怎么办为了解决这个问题我们可以遍历一遍原数列找出里面的最大值和最小值接着我们就可以创建一个最大值 - 最小值 1大小的数组接着我们遍历原数组统计元素出现次数的时候就可以减去一个最小值最后还原原数组的时候再把这个最小值加上这样我们就同时达到了优化空间大小于解决负数的两个问题下面是代码实现//计数排序 void CountSort(SortDataType* a, int n) { int max a[0], min a[0]; for (int i 1; i n; i) { if (a[i] max) { max a[i]; } if (a[i] min) { min a[i]; } } int range max - min 1; SortDataType* count (SortDataType*)malloc(sizeof(SortDataType) * range); if (count NULL) { perror(malloc fail!); return; } memset(count, 0, sizeof(SortDataType) * range); //映射下标 for (int i 0; i n; i) { count[a[i] - min]; } int j 0; for (int i 0; i range; i) { while (count[i]--) { a[j] i min; } } free(count); count NULL; }尽管我们对空间有优化但这个算法还是不太适合数据范围过大的情况下所以这个算法还是要看场景来使用。接着我们就可以测试一下上面我们写的算法进行一个对比冒泡太慢了我就把它给踢出去了数据量统一为100w3.各个排序算法稳定性讨论衡量一个排序算法是否稳定的标准是相同大小的元素是否在经过排序后相对位置不发生改变比如原数组有两个2 原本前面的2在排序过后还在原本后面的那个2前面相信很好理解我这里就不画图说明了因为写到这里我真的挺累的。下面是针对各个算法的稳定性讨论其实我们回忆一下这个算法的核心思想就很容易判断出这个排序算法是否是一个稳定的排序算法。插入排序如果两个元素是相同大小的话后面的那个元素在排序是就直接插入到前面的那个元素的后面并没有改变相对位置所以是一个稳定的排序希尔排序希尔排序就不用所了相同的两个元素可以在预处理阶段被分到不同的组里前面的那个元素可能被换到后面所以这个排序不是一个稳定的排序算法选择排序这个排序其实是一个不稳定的排序但是有些教科书上面写的是稳定排序我一开始也是搞错了所以还是要多画图理解我们可以举个例子可以看到选小的放前面蓝色的被调到后面了相对位置发生了变化所以这是一个不稳定的排序堆排序这个不用说假如里面都是2的话第一个2会被换到最后面所以是一个不稳定的排序冒泡排序根据我们前面对冒泡排序的小优化就可以知道当不在交换时就以及有序了而当我们要排升序时如果前面有相同或者比它大的元素时我们是不会让这个元素换到后面的不然我们的优化还有什么意义呢所以冒泡排序是一个稳定的排序快速排序这个也可以很容易举出反例因此快速排序也是一个不稳定的排序算法归并排序我们回忆一下归并算法的过程会发现在归并的过程中并不会改变两个相同元素的相对位置所以归并排序也是一个稳定的排序总结排序大类算法名称时间复杂度空间复杂度稳定性插入排序直接插入排序O(N²)O(1)稳定插入排序希尔排序O(N^1.3)O(1)不稳定选择排序选择排序O(N²)O(1)不稳定选择排序堆排序O(N*logN)O(1)不稳定交换排序冒泡排序O(N²)O(1)稳定交换排序快速排序O(N*logN)O(logN)不稳定归并排序归并排序O(N*logN)O(N)稳定写这篇博客我耗费了好多的时间但慢就是快踏踏实实的好好总结遍还方便后面拿来复习后面我会陆陆续续的系统性更新C的内存