给自己的家乡建设网站,长春网站排名优化价格,90设计网站终身会员,长沙网站建设哪家好【数据结构】——十大排序详解分析及对比 文章目录 【数据结构】——十大排序详解分析及对比前言1. 排序的概念及其运用1.1 排序的概念1.2 排序的应用 2. 插入排序2.1 直接插入排序2.2 希尔排序 3. 选择排序3.1 选择排序3.2 堆排序 4 交换排序4.1 冒泡排序4.2 快速排序4.2.1 霍…【数据结构】——十大排序详解分析及对比 文章目录 【数据结构】——十大排序详解分析及对比前言1. 排序的概念及其运用1.1 排序的概念1.2 排序的应用 2. 插入排序2.1 直接插入排序2.2 希尔排序 3. 选择排序3.1 选择排序3.2 堆排序 4 交换排序4.1 冒泡排序4.2 快速排序4.2.1 霍尔法4.2.2 前后指针法4.2.3 优化方法4.3.4 快排(非递归) 5. 归并排序5.1 归并(递归)5.2 归并(非递归)5.3 外排序 6. 非比较排序6.1 计数排序6.2 基数排序6.3 桶排序 结语 前言
排序算法是《数据结构》中最基本的算法之一
我们先来大致简单了解一下排序算法吧
排序算法可以分为内部排序和外部排序内部排序是数据记录在内存中进行排序而外部排序是因排序的数据很大一次不能容纳全部的排序记录在排序过程中需要访问外存
根据排序的特点可以将排序分为直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序等 1. 排序的概念及其运用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的
内部排序数据元素全部放在内存中的排序外部排序数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序 1.2 排序的应用
排序在日常生活当中很常见 比如班级成绩排名学校排名地区GDP排名等等都是排序 这个就是学校排名的实列像这样的排序例子还有非常多咱就不一一介绍了哈
感兴趣的可以看看
2. 插入排序
2.1 直接插入排序
我们先来看看动图展示认识一下直接插入排序 看动图是不是非常地简单不就是一个一个比较大小嘛接下来我们来看看直接插入排序的基本思想
基本思想
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移
其实不就是先将左边的第一数当作是有序的然后把第二个数作为插入数从右往左与有序区间中的每个数做比较
这时会出现两种情况如果插入数比该数小则该数往后挪动插入数继续向左比较如果插入数比该数大则说明插入数找到了插入有序区间的位置直接插入。以此类推直到最后一个数插入后就完成了排序
下面就是代码实现
void InserSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];//保存插入数while (end 0)//对比直到最后一个数{if (a[end] tmp)//比插入数大{a[end 1] a[end];//后移end--;//更新比较数}else{break; }}a[end 1] tmp;//插入数据}
}算法分析
时间复杂度
最坏情况:逆序每次插入的数都是有序数组最小的比较次数:123…n1(n-1)*n/2大O渐进表示法0(N^2)最好情况:顺序有序经有序遍历一次数组即可大O渐进表示法O(N)
平均情况:介于**O(N)~((N^2)**之间
空间复杂度
只开辟常数级别空间 O(1)
稳定性
遇到相等的数放在后面稳定
2.2 希尔排序
希尔排序其实就是对插入排序进行优化也就是插入排序的pro max
我们先来看看动图展示认识一下希尔排序 基本思想
先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好
前面我们说了当数组是有序的时候插入排序的时间复杂度是O(N)
那我们可不可以想办法让数组接近有序呢?这样我们再进行一组插入排序的时候时间复杂度也基本会接近O(N)
这时一个叫希尔的人就提出了预排序的概念
希尔排序也就是分为两步
预排序目的是让数组接近有序直接插入排序
那预排序如何做到让数组接近有序呢?
如果我们一组数据分成gap组。每组数据都是在数组中相隔gap位置的数据组合如果我们让每一组都使用插入排序排好后那数组就会比原来更接近有序
举个例子假如我们用希尔排序排 6,2,4,1,8,0,3,9,7,5 这个数组
当 gap 3 就把数组分为了三组那第一组来说第一组是 6135 按照直接插入排序来排的话结果就是 1356
当 gap 3 的所有分组都排序后数据就更接近有序
这时数组可能还是没那么有序所以我们会进行多次分组排序 现在我们再来一次 gap 2 的预排序看看是不是发现预排序后数组已经非常接近有序了 这时候我们在来一次插入排序( gap 1 就是直接插入排序)就完成数组的希尔排序 这时我们是不是感觉希尔排序要比直接插入排序好用一些呀
我们会发现又有一些新问题出现了gap该怎么合理取值我们会发现
gap越大的话大的数越快跳到后面小的数越快跳到前面但是这样就越不接近有序。例如200个数据 gap100 这样每组的数据只有两个然后把每组的最大的放在前100个位置最小的放在后100个位置这样预排序的效果不太好万一每组的两个数组是最大或第二大的数那这样第二大数放在了最小数的位置。最大的数也才放在中间的位置gap越小的话也接近有序gap1的时候就是插入排序。但是太小就达不到预排序让数组接近有序的目的了
因此我们希望gap是变化的同时gap有两种取值
gapgap/2gapgap/3
我们实验发现 gap/3 的时候预排序的效果是比较好的但是 gap/3 最后不一定能保证gap1怎么办呢
所以 gapgap/31 这样一定能保证gap最后一定是1。为什么?大家想一个数一直除3那么最后他一定会被除到0那么0又是由 gap/3 得来的。所以最后一次/3前gap一定是1或2其中个取值如果是1的话刚好是预排序但是如果是2最后一次排序就不是预排序但是我们1就算最后一次是2。2/311 也能保证最后一次是1当gap是1时就是插入排序就能保证最后一次排序一定是插入排序
下面就是代码实现
void ShellSort(int* a, int n)
{int gap n;while (gap 1){//1保证最后一次一定等于1//gap1是预排序//gap1是插入排序gap gap / 3 1;for (int i 0; i n - gap; i)//多组一起排{int end i;int tmp a[end gap];//保存插入数while (end 0)//对比直到最后一个数{if (a[end] tmp)//比插入数大{a[end gap] a[end];//后移end--;//更新比较数}else{break;}}a[end gap] tmp;}}
}算法分析
时间复杂度
希尔排序的时间复杂度不好计算因为gap是变化的。且前面都排序会对导致很难去计算因此在好多书中给出的希尔排序的时间复杂度都不固定但是目前公认希尔排序的时间复杂度大概在 O(N^1.3) 左右 我们来简单证明看一下
这里为了方便证明我们先把gap看作 gapgap/3 变化 n个数据排序 第一次组数gap n/3 每组数据个数n/gap 3
最坏情况逆序
插入比较次数等差数列 12 3
所有组排完消耗n/3*3n
第二次组数gap n/3/3 n/9 每组数据个数n/gap n/n/9 9
最坏情况逆序
插入比较次数等差数列 123…8 36
所有组排完消耗n/9*36 4n
……
那后面的组我们好像也可以按照这样的规律计算出来
因为排序每组消耗是等差数列gap组数我们也可以算但是问题在于我们第一次排序是逆序排序完后他还可能是逆序吗?
显然不是所以后面我们就不能按照最坏情况去算等差数列也就不存在了。这就需要涉及数学的概率论等更高深的知识了已经超出我的数学水平了 所以我们只知道第一次排序和最后一次排序每趟排序消耗都是n中间每趟排序只能猜测大概是先增后减具体如何变化还需要涉及更深的数学知识。
不过经过一些测试希尔排序的时间复杂度大概是 O(N^1.3) 左右
但是我们知道走了多少次预排序
如果gap/2那就是gap/2/2/2…1结束如果gap/3就是gap/3/3/3…1结束
所以预排序的次数是对数级别
我们只能记住结论希尔排序的时间复杂度大概在 O(N^1.3) 左右就好了
空间复杂度
只用到常数级别空间O(1)
稳定性 相同的数据分到不同组时候不可控制不稳定
3. 选择排序
3.1 选择排序
我们先来看看动图展示认识一下选择排序 看动图是不是有点了解了接下来我带着大家看看选择排序的基本思想
基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素
简单来说就是遍历一遍数组找出最小数然后将未排序区间的第一个数与最小的数交换
以此类推每次都能排序一个数直到最后一个数选择排序就完成了
下面就是代码实现
我们发现代码的时间复杂度太差了所以代码实现我们做了一点优化每一次遍历确定一个最小数和最大数然后分别放在未排序区间的末尾和开始位置即可
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int max begin, min end;for (int i begin 1; i end; i){if (a[i] a[max])//找最大值{max i;}if (a[i] a[min])//找最小值{min i;}}Swap(a[begin], a[min]);if (max begin)//若max与begin重叠{max min;}Swap(a[max], a[end]);begin;end--;}
}不过要注意的是如果我们先交换最小的数如果max和begin位置重叠begin被交换后。max也被交换了所以要重新更新一下 max min
算法分析
时间复杂度
时间复杂度为 O(N^2)
每次遍历选出2个数遍历n/2次即可 n-1n-3…1(n-11)/2*n/2n~2/4. 大O渐进表示法 O(N^2)
空间复杂度
只用了常数级别空间O(1)
稳定性 如图不稳定
3.2 堆排序
我们先来看看动图展示认识一下堆排序 看完动图是不是感觉有点懵别急我们来看看堆排的基本思想
基本思想
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆
将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆这样会得到n个元素的次小值。如此反复执行便能得到一个有序序列了
堆排序就是利用堆顶数据是最大或最小这一特性进行排序每次都把堆顶元素放在待排序区间后面然后重新调整建堆以此类推即可完成排序
下面就是代码实现
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;//孩子节点while (child size){if (child 1 size a[child] a[child 1])//孩子节点{child;}//假设法if(a[child] a[parent])//判断{Swap(a[parent], a[child]);//交换parent child;child parent * 2 1;}else{break;//调整完毕}}
}
void HeapSort(int* a, int n)
{for (int i (n - 1 - i) / 2; i 0; i--)//向下调整建堆{AdjustDown(a, n, i);}int end n - 1;//最后一个堆元素while (end 0){Swap(a[0], a[end]);//交换堆顶元素和最后一个堆元素AdjustDown(a, end, 0);//交换堆顶元素和最后一个堆元素end--;//更新最后一个堆元素}
}算法分析
时间复杂度
堆排序的时间复杂度是 O(N*logN)
构建初始堆经推导复杂度为O(n)在交换并重建堆的过程中需交换n-1次而重建堆的过程中根据完全二叉树的性质[log(n-1),log(n-2)…1]逐步递减近似为n*logn
我们来简单的证明一下 空间复杂度
只用到常数级别空间O(1)
稳定性 如图不稳定
4 交换排序
4.1 冒泡排序
我们先来看看动图展示认识一下冒泡排序 看完动图是不是感觉冒泡排序也是非常简单的接下来我们看看冒泡排序的基本思想
基本思想
交换排序就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动
从左边开始两两比较将大的数移到右边再往后两两比较这样每都选出一个待排序区间最大的数进行n-1躺排序就能完成数组有序
接下来就是代码实现
void bubble_sort(int arr[],int sz)
{for (int i 0; i sz - 1; i)//控制趟数{int flag 0;for (int j 0; j sz - 1 - i; j)//控制比较次数{if (arr[j] arr[j 1])//判断是否交换{flag 1;Swap(arr[j], arr[j 1]);//交换}}if (flag 0)break;//已经排好序直接结束循环}
}其实代码也没什么好说的这里我们用flag做优化如果发生交换就标记一下然后每次循环判断一下标记如果没有标记说明没发生交换说明已经有序直接break结束就可以了
算法分析
时间复杂度
最坏情况下比较总数n-1n-2…1(n-11)/2*(n-1)大O渐进表示法O(N^2)
冒泡排序的时间复杂度是 O(N^2)
空间复杂度
只开辟常数级别空间 O(1)
稳定性
只让大的数交换到右边。相等的数不交换稳定
4.2 快速排序
快速排序我们这里介绍两种快排的方法以及如何进行快排的优化方案
4.2.1 霍尔法
我们先来看看动图展示认识一下快速排序(霍尔法) 其实看动图挺懵的接下来让我们一起看看快速排序(霍尔法)的基本思想吧
基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止
对于一组数据选择一个基准元素key通常选择第一个或最后一个元素我们就选择第一个元素作为我们的基准元素然后定义一个左指针和右指针左指针往右找大右指针往左找小。找到后交换左右指针的位置数据直到左右指针相遇。然后将key与相遇数据位置交换。这样key左边都是小于key的数右边都是大于key的数。就完成了key的排序再有同样的方法递归排序左右区间直到序列中所有数据均有序为止
但是得保证相遇位置一定比key小才可以保证左边区间有序现在就有一个问题如何证明相遇位置一定比key小呢
我们可以简单说一下
第一个元素做key右边先走可以保证相遇位置比key小
相遇只有两种场景
L遇R
R先走遇到比key小的位置停下L再走找不到比key大的数遇到R结束R的位置就是比key小的位置 R遇L
R先走找小没有找到比key小的直接和L相遇了L的位置是上一轮交换的位置交换完后的位置L的位置就是比key小的数。此时R和L相遇相遇的位置就是L的位置也就是比key小的数位置 相反当最后一个元素做key左边left先走时能保证相遇的位置比key大
接下来就是代码实现
int PartSort1(int* a, int left, int right)//霍尔法
{int begin left, end right;int keyi left;//keyi为左 右先走 keyi为右 左先走while (begin end){while (begin end a[end] a[keyi]){--end;}while (begin end a[begin] a[keyi]){begin;}Swap(a[begin], a[end]);//两个都找到交换}Swap(a[keyi], a[begin]);//相遇交换keyi和相遇的数return begin;//keyi移动到相遇位置
}
void QuickSort(int* a,int left,int right)//递归
{if (left right)//区间不存在结束递归{return;}else{int keyi PartSort1(a, left, right);QuickSort(a, left, keyi - 1);//递归左序列QuickSort(a, keyi 1,right);//递归右序列}
}我们这边也是用到了递归的方法我们也就来顺便画一下递归展开图加深一下理解 4.2.2 前后指针法
我们先来看看动图展示认识一下快速排序(前后指针法) 观看动图我们依然能感觉到快排的思想不过这个方法就比霍尔法容易理解得多我们还是来看看基本思想看看我说的对不对
基本思想
既然快排的每一趟都是分割好左右区间并且排好key那我们就可以区间思想来完成这个事情就是前后指针法目的分成左右区间 我们让slow指针维护key区间fast遍历扫描遇到比key小的位置停下然后放到slow的位置slowfast继续扫描。这样就形成这样的区间 最后将key和slow交换即可 接下来就是代码实现
int PartSort2(int* a, int left, int right)//快慢指针法
{int slow left, fast slow 1;int keyi left;while (fast right){if (a[fast] a[keyi] slow!fast ){slow;//扩大区间Swap(a[fast], a[slow]);//交换}fast;//扫描}Swap(a[keyi], a[slow]);//交换return slow;
}
void QuickSort(int* a,int left,int right)//递归
{if (left right)//区间不存在结束递归{return;}else{int keyi PartSort2(a, left, right);QuickSort(a, left, keyi - 1);//递归左序列QuickSort(a, keyi 1,right);//递归右序列}
}算法分析
时间复杂度
二分区间递归 logN 层每层总和消耗可以看作遍历数组N大O渐进表示法 O(N*logN)
快速排序的时间复杂度是 O(N*logN)
空间复杂度
递归深度 logN开辟 O(logN) 栈空间。
稳定性
交换key和相遇位置时相遇位置大小和左区间大小不确定不稳定
4.2.3 优化方法
快排的基本代码实现我们已经完成了不过现在的快排在一些特殊场景下效率会降低所以我们就给出了几个优化的方法
方法一三数取中
当key趋近中间值时每次基本都是二分区间当区间二分为只剩一个数时就排好序了我们把每层消耗都看作遍历一次数组(实际是往下一次减1)时间复杂度就是O(N*logN) 如果key的大小趋近最大或最小会是什么情况呢 key趋近最大或最小每层递归都只能确定一个数需要递归N层每层消耗递减也就是等差数列时间复杂度O(N^2)
所以我们选key是要尽量避免key过大或过小的情况然后就有大佬提出了三数取中的方法其法就是在数组最左端和最右端和中间位置取三个数然后选出三数的中间大小的那个数作为key即可这样至少能保证选出的数不会是最大或最小的情况
这样也是在保证这三个数趋近于数组元素的大中小的情况下如果这三个数都比较小或大那效率也会很低这样容易被针对所以最优的做法是随机选出三个数在进行三数取中这样适应性更强
接下来是代码实现
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;// left midi rightif (a[left] a[midi]){if (a[midi] a[right]){return midi;}else if (a[left] a[right]) // a[midi] a[right]{return right;}else{return left;}}else // a[left] a[midi]{if (a[midi] a[right]){return midi;}else if (a[left] a[right]) // a[midi] a[right]{return left;}else{return right;}}
}方案二小区间优化
我们会发现我们想让五个数有序还需要递归七次还需要递归三层 我们知道最后一层递归大约占递归总数的50%最后三层大约占了80%的递归递归需要建立栈帧还是有消耗的
所以当递归区间只剩10个数左右我们就不需要再递归排序了我们使用其他排序希尔针对数据量小的时候预排序发挥不出作用堆排序建堆就已经O(N)了所以我们选择O(N^2)中最优的插入排序
这就是小区间优化接下来是代码实现
void QuickSort(int* a,int left,int right)//递归
{if (left right){return;}//小区间优化if (right - left 1 10){InserSort(a left, right - left 1);}else{int keyi PartSort2(a, left, right);QuickSort(a, left, keyi - 1);//递归左序列QuickSort(a, keyi 1,right);//递归右序列}
}方案三三路划分
三路划分是什么意思我们会发现当数据中有大量重复数据时我们不论是三数取中还是随机数选key都有极大可能选到重复数据这样就导致分割区间就会很偏效率低下其实要是很多重复数据我们只要将重复数据放在一个区间那就只需要完成其左右区间即可效率就会大幅提升 当面对有大量跟key相同的值时三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段【比key小的值】【跟key相等的值】【比key大的值】所以叫做三路划分算法
结合一下图理解一下实现思想
key默认取left位置的值left指向区间最左边right指向区间最后边cur指向left1位置cur遇到比key小的值后跟left位置交换换到左边leftcurcur遇到比key大的值后跟right位置交换换到右边right–cur遇到跟key相等的值后cur直到curright结束
void PartSort3(int* a, int begin, int end)//三路划分
{if (begin end){return;}//小区间优化if (begin - end 1 10){InserSort(a begin, end - begin 1);}else{int mid GetMid(a, begin, end);//随机数三数取中Swap(a[mid], a[begin]);int left begin, right end;int cur left 1;int key a[left];while (cur right){if (a[cur] key){Swap(a[left], a[cur]);cur;left;}else if (a[cur] key){Swap(a[cur], a[right]);right--;}else{cur;}}PartSort3(a, begin, left - 1); // 递归左区间PartSort3(a, right 1, end); // 递归右区间}
}代码看看就好了不用太过纠结主要是体会其思想
4.3.4 快排(非递归)
我们说了上面两种方法都是通过递归实现的那如果采用非递归的方式应该如何实现呢
递归其实最重要的就是参数其实只要我们知道的递归的参数并保存起来那我们就只要对那段区间进行快排分割即可那如何保存呢?这就可以借助栈和队列来做
栈先把左右区间入栈然后快排分割区间后。将两个区间入栈(先后不影响)再去取栈顶的两个元素就得到了一个待排序区间继续快排分割又得到两个区间继续入栈。以此类推知道栈为空结束就完成排序 队列队列的思路和栈也是一样的都是为了保存递归的参数。不同的是队列是一层一层的排序就是栈的是先往深的排序再回退到右边排序
接下来是代码实现
void QuickSortNonR(int* a, int left, int right)//非递归
{ST st;STInit(st);STPush(st, right); // 入栈STPush(st, left); // 入栈while (!STEmpty(st)) // 栈不为空{int begin STTop(st); // 右端点STPop(st); // 出栈int end STTop(st); // 左端点STPop(st); // 出栈int keyi PartSort2(a, begin, end); // 分割if (keyi 1 end) // 判断区间存在{STPush(st, end); // 区间入栈STPush(st, keyi1);}if (begin keyi - 1) // 判断区间存在{STPush(st, keyi - 1); // 区间入栈STPush(st, begin);}}STDestroy(st); // 销毁栈
}5. 归并排序
5.1 归并(递归)
我们先来看看动图展示认识一下归并排序 看完动图我们发现归并排序还是挺简单的接下来我说一下基本思想吧
基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序
简单来讲就是将数组看作两个有序区间然后将两个有序区间合并成一个新的有序区间
我们可以新开辟一块原数组的大小空间然后定义两个指针分别指向两个区间的开头保证两个都是该区间最小的数比较指向的两个数把最小的尾插到新数组然后小的数指针向前移动继续比较直到两个指针有一个越界。但是比较完后另一个区间至少还有一个数此时越界区间已经没有比另外一个区间最小的数还小的数又因为区间是有序的所以将未越界区间剩余的数尾插到数组即可完成排序
至于刚开始的数组是乱序的我们就可以选择一个合理的区间先递归左区间和右区间再归并 接下来是代码实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin end){return;}int mid (begin end) / 2;// 如果[begin, mid][mid1, end]有序就可以进行归并了_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid1, end);// 归并int begin1 begin, end1 mid;int begin2 mid1, end2 end;int i begin;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 begin, tmp begin, (end - begin 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp NULL;
}我们这边也是用到了递归的方法我们也就来顺便画一下递归展开图加深一下理解 哎这时有小伙伴就要问了分割区间的时候为什么是 [begin, mid] [mid1, end] 呀我觉得 [begin, mid-1] [mid, end] 这样分割区间也行啊
好我们来假设区间是 [2, 3] 这样会更容易陷入死循环为什么呢让我们来好好分析一下 算法分析
时间复杂度
二分区间递归log层每层消耗看作遍历一次数组N大O渐进表示法 O(N*1ogN)
所以归并排序的时间复杂度是 O(N*1ogN)
空间复杂度 开辟N个数的空间 O(N)
稳定性 将数据相同的左区间数据尾插即可 稳定
5.2 归并(非递归)
其实归并也可以用循环控制我们把一个数看作一个区间然后一一归并。这样就形成了若干个区间为二的有序区间继续两两归并又形成若干个区间为四的区间四四归并……直到区间数大于原数组个数就完成了排序 接下来就是代码实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}// gap每组归并数据的数据个数int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){// [begin1, end1][begin2, end2]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// 第二组都越界不存在这一组就不需要归并if (begin2 n){break;}// 第二的组begin2没越界end2越界了需要修正一下继续归并if (end2 n){end2 n - 1;}int j i;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(int) * (end2 - i 1));}printf(\n);gap * 2;}free(tmp);tmp NULL;
}算法分析
时间复杂度
二分区间递归log层每层消耗看作遍历一次数组N大O渐进表示法 O(N*logN)
所以归并排序的时间复杂度是 O(N*logN)
空间复杂度
开辟N个数的空间O(N)
稳定性
将数据相同的左区间数据尾插即可稳定
5.3 外排序
其实归并排序在实践中是非常实用的归并为什么实用我们得首先了解一下外排序
归并排序既可以做内排序也可以做外排序
外排序是指能够处理极大量数据的排序算法。通常来说外排序处理的数据不能⼀次装入内存只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采⽤的是⼀种“排序-归并”的策略。在排序阶段先读入能放在内存中的数据量将其排序输出到⼀个临时文件依此进行将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时⽂件组合为⼀个大的有序⽂件也即排序结果
跟外排序对应的就是内排序我们之前讲的常见的排序都是内排序他们排序思想适应的是数据在内存中⽀持随机访问。归并排序的思想不需要随机访问数据只要依次按序列读取数据所以归并排序既是⼀个内排序也是⼀个外排序
如果数据量很大那么我们就不能再内存中排序了毕竟内存大小有限这时我们就可以借助归并排序的外排序思想在磁盘中读取文件排序我们可以先读取n个数据的两个文件的数据然后将两个文件排序后归并到新的文件。这样新的文件继续和读取n个数据的文件归并一次类推当数据全部读取完完后就得到一个排好序的文件了
文件归并排序基本思想
读取n个值排序后写到file1再读取n个值排序后写到file2file1和file2利用归并排序的思想依次读取比较取小的尾插到mfilemfile归并为一个有序文件将file1和file2删掉mfile重命名为filel再次读取n个数据排序后写到file2继续走file1和file2归并重复步骤2直到文件中无法读出数据。最后归并出的有序数据放到了file1中 其实基本思想还是挺简单的这个了解思想即可至于代码实现的话对于目前来说没有那么重要
6. 非比较排序
6.1 计数排序
我们先来看看动图展示认识一下计数排序 其实动图的话计数排序还是挺好理解的接下来我们来说说基本思想
基本思想
统计相同元素出现次数 count[a[i]]根据统计的结果将序列回收到原来的序列中 排序
本质上就是利用在count数组的自然序号排序
写代码之前我们还得注意一点小细节
像 0123456789 这样的数组我们只用开辟10个数组空间就行了
但是像 100101102103104105106107108109 这样的数组我们如果开辟110个数组空间会不会就显得非常浪费空间
所以我们采用相对映射的方式找出最大值和最小值开辟 [ 最大值 - 最小值 1 ] 个数据的空间遍历数组数据存放到下标为 [ 数据 - 最小值 ] 的位置写数据时数据的大小就是 [ 数组下标 最小值 ] 接下来就是代码实现
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 1; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;int* count (int*)calloc(range, sizeof(int));if (count NULL){perror(calloc fail);return;}// 统计次数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);
}算法分析
时间复杂度
遍历一遍数组O(N)。同时再遍历一次开辟数组同时写入N个元素元素时间复杂度大O渐进法表示O(N)
所以计数排序的时间复杂度是 O(N)
空间复杂度
开辟N个空间 O(N)
再来两个几乎用不到的排序讲一下思想即可
6.2 基数排序
我们先来看看动图展示认识一下基数排序 看完动图来说还是比较简单的接下来就简单讲一下基本思想吧
基本思想
将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数
6.3 桶排序
我们先来看看动图和图片的展示认识一下基数排序 其实光看动图还是有点难以理解但是有了图片的帮助就不一样了感觉非常清晰接下来我来简单讲讲基本思想
基本思想
设置一个定量的数组当作空桶遍历输入数据并且把数据一个一个放到对应的桶里去对每个不是空的桶进行排序从不是空的桶里把排好序的数据拼接起来
结语
我们最后来看看各个排序的对比吧 好了感谢你能看到这里本篇到这就结束了希望对你有所帮助
溜了溜了我们下篇文章再见吧
