网站关键字描述,莆田制作公司网站,网站建设需要什么条件,wordpress的cms插件 目录 一、排序的概念及其运用1.1 排序的概念1.2 排序的应用1.3 常见的排序算法 二、常见排序算法的实现2.1 插入排序2.1.1 直接插入排序2.1.2 希尔排序2.1.3 直接插入排序和希尔排序的性能对比 2.2 选择排序2.2.1 直接选择排序2.2.2 堆排序2.2.3 直接选择排序和堆排序的性能… 目录 一、排序的概念及其运用1.1 排序的概念1.2 排序的应用1.3 常见的排序算法 二、常见排序算法的实现2.1 插入排序2.1.1 直接插入排序2.1.2 希尔排序2.1.3 直接插入排序和希尔排序的性能对比 2.2 选择排序2.2.1 直接选择排序2.2.2 堆排序2.2.3 直接选择排序和堆排序的性能对比包括前面 2.3 交换排序2.3.1 冒泡排序2.3.2 快速排序2.3.2.1 递归实现2.3.2.2 非递归实现 2.3.3 冒泡排序和快速排序的性能对比包括前面2.3.4 快速排序优化 2.4 归并排序2.4.1 递归实现2.4.2 非递归实现2.4.3 归并排序优化2.4.4 归并排序的应用——外排序 三、排序算法复杂度及稳定性分析3.1 稳定性的意义3.2 稳定性分析3.3 排序算法时间、空间复杂度和稳定性比较表格 个人专栏 《数据结构世界》 一、排序的概念及其运用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序的应用 1.3 常见的排序算法 二、常见排序算法的实现
2.1 插入排序
基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
其实我们玩扑克牌时就用到了插入排序的思想
2.1.1 直接插入排序
假设tmp为我们要插入的牌我们往[0, end] 这个有序区间中比较插入 这里排升序
如果end位置的元素大于tmp则将该元素向后挪动一位end–如果小于tmp则break跳出循环将tmp插入end1的位置循环的条件end 0如果end的元素一直大于tmp那end最后就会减到-1 代码实现 上述是插入一次数据的过程那如果我要对一个数组进行排序呢很简单先取数组的第二个元素进行插入排序再取第三个……依此类推循环上述过程即可完成对数组的排序。 运行结果
先简单写个打印数组函数 时间复杂度分析
O(N2) —— 最坏逆序O(N) —— 最好顺序
从上述分析可以看出如果要排序的数据越接近有序则使用直接插入排序的时间效率越高。
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[i 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}2.1.2 希尔排序
上述分析给予我们启发如果我让要排序的数据先接近有序再用直接插入排序那不就皆大欢喜了吗 而就是一位叫希尔的大佬付诸了行动希尔排序主要分为两步
预排序 —— 接近有序直接插入排序
那么什么叫做预排序呢简单来说分为两步
对数据进行分组。间隔为gap的数据分为一组总计gap组分别对每组数据插入排序
举个例子 假设 gap3 那么我们就可以分成红蓝绿3组每组间距为3。那么我们对每组进行插入排序就会变成下图的情况。这样做可以节省时间比如9原本到后面要9次现在只用3次即可因为每次都跨越gap步
有了前面直接插入排序的经验我们就很容易实现一组的插入排序比如红色只用将间距从1变成gap即可。 那么我们要实现对每一组都排序只要在外层套一层循环即可。因为有gap组所以循环gap次。 先测试一下预排序运行结果 预排序功能基本实现但是其实我们还可以简化一下代码减少一层循环只需要小小的改动一下。 大家可以仔细思考其中的差异。其实思想转变很简单原本是红绿蓝一组一组排现在是多组并排但是时间效率是相等的。 完成了预排序的实现我们再来看看gap的取值。
gap 1时恰好就是直接插入排序gap 1时才是预排序
同时我们发现gap越大预排序速度越快但越不接近有序gap越小预排序速度越慢但越接近有序。 所以gap的取值应该不断变化n很大时gap也大预排序快速而后面不断排序的过程中为保证接近有序gap应该逐步减小最后gap为1就是直接插入排序。
实现代码如下 这里gapgap/3 1中的1保证了最后一次gap一定为1也就是循环中先预排序最后一次直接插入排序。单个代码实现双重含义简洁明了。
运行结果 所以总结一下希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后gap不断变小重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。
void ShellSort(int* a, int n)
{int gap n;while (gap 1){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 - gap;}else{break;}}a[end gap] tmp;}}
}2.1.3 直接插入排序和希尔排序的性能对比
既然说希尔排序是直接插入排序的升级版那能比它快多少呢那我们就来实际测试一下release版本。
先动态开辟两个数组再随机生成10w个随机数分别存入其中 使用clock函数clock函数可以给出系统开机到现在的时间记录每个排序所用的时间打印数据进行对比并释放数组空间 运行结果 这样看来是不是希尔排序比起直接插入排序优化了非常多啊 时间复杂度分析
希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在很多书中给出的 希尔排序的时间复杂度都不固定。
《数据结构(C语言版)》 — 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 因为我们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(n1.25)到O(1.6 * n1.25)来算
2.2 选择排序
基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 2.2.1 直接选择排序
这里我们对前面的思想进行一点小小的优化一次分别选出最小和最大的元素分别放在起始和末尾。
我们先定义开头和结尾的下标并默认最小下标为开头和最大下标为结尾循环遍历一遍如果遇到比a[mini]更小的数则下标更新mini i 同样如果遇到比a[maxi]更大的数则 maxi i遍历结束后进行交换最小的数放在开头最大的数放在结尾 这里因为频繁使用交换所以独立写了一个交换函数。 上述只是一次遍历选择而要排序完整个数组只需在外层套上一层循环即可。 注意要把mini和maxi放进循环中因为begin和end会不断更新 运行结果 但是我们居然发现排序结果居然不对这是为什么呢
其实有一种特殊情况我们并没有考虑到请看下图。 如果maxi和begin重叠那么就会出问题因为在maxi交换前它的值已经被替换了。那我们应该怎么改呢只需要更新一下maxi即可。 正确的运行结果 时间复杂度分析
O(N2)直接选择排序思考非常好理解但是效率不是很好。实际中很少使用
void Swap(int* e1, int* e2)
{int tmp *e1;*e1 *e2;*e2 tmp;
}void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi end;for (int i begin; i end; i){if (a[mini] a[i]){mini i;}if (a[maxi] a[i]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
}2.2.2 堆排序
关于堆排序在往期的【数据结构】【版本2.0】【树形深渊】——二叉树入侵 有详细讲解这里简单归类一下不再讲具体实现。
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 运行结果
时间复杂度分析
O(N*log2N)堆排序使用堆来选数效率就大大提高了
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){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 - 1) / 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--;}
}2.2.3 直接选择排序和堆排序的性能对比包括前面
既然堆排序是选择排序中的强者希尔排序又是插入排序的精英谁能更胜一筹呢直接插入排序与直接选择排序相比谁又能做第二把交椅呢请看下面测试release版本。
数据量为10w时 数据量为100w时 经过上述代码测试我们可以轻易发现希尔排序和堆排序在伯仲之间而在O(N2)的排序算法中插入排序还是有不错的适应性的但是选择排序就效率太低了上不了台面。
2.3 交换排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 2.3.1 冒泡排序
冒泡排序是最简单的排序而且方便理解具有教学意义也是我们学的第一个排序算法。早在往期的指针章节 不允许你还不了解指针的那些事二已经详细讲解这里也是简单归类一下。
冒泡排序的核心思想就是两两相邻的元素进行比较 运行结果 时间复杂度分析
O(N2) —— 最坏逆序O(N) —— 最好顺序
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){bool exchange false;for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;exchange true;}}if (exchange false){break;}}
}2.3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 2.3.2.1 递归实现
这里我们可以用分治的思想来递归实现。
返回条件区间长度为0或者区间不存在则return子问题转换为 [ begin, keyi - 1 ] keyi [ keyi 1, end ] 来进行分治每次确定基准值再递归进入被切割的左右子序列。
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像所以快速排序叫做二叉树结构的交换排序方法。 而实现按基准值切割左右子序列这里有三种实现版本
hoare版本左右指针法
这个方法是最初hoare实现快速排序的版本。 主要思路
先确定基准值key一般选取最左边的元素作为基准值先从右边开始找比key小的元素再从左边开始找比key大的元素二者交换循环重复步骤2直到 left 和 right 相遇最后将基准值与相遇位置元素交换
这里有几个值得注意的点
如果确定最左边元素为key则右边先找如果确定最右边元素为key则左边先找如果不满足大家可以对照动图自行画图感受一下大家可能会疑惑为什么最后相遇的位置一定比key小呢这就是值得探讨的核心实际上这就是由前面一点所决定的左边做key右边先走就保障了相遇的值一定小于等于key。
相遇无非两种情况L遇RR遇L
L遇R也就是上述动图的情况。L走之前R已经停下来了那么R已经找到比key小的值所以相遇的值比key小R遇LR走之前有两种情况。L还没走就是key 或者 L在上一轮循环中已经交换到比key小的值所以相遇的值小于等于key
所以这样就证明了左边做key右边先走就保障了相遇的值一定小于等于key。
还有一个点就是左右在寻找的过程中有可能一直找不到造成越界访问所以里面循环也要加上left right进行限制最后还要注意如果遇到的值等于key可能会导致死循环所以等于key时左右指针也继续走如下图 //Hoare版本
int PartSort1(int* a, int left, int right)
{int keyi left;while (left right){while (left right a[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}挖坑法
但是由于hoare版本有很多需要考虑周全的地方所以又流传出了一种简化的版本比较便于理解。 主要思路
同样以最左边为基准值key但是我们创建临时变量将其存储起来那么最左边就变成了“坑位”那么就很自然地因为左边为坑位所以从右边开始找找到比key小的值填补到坑位里再将自身变成坑位那么坑位在右我们就从左边开始找找到比key大的值填补到坑位里再将自身变成坑位最后再将key填补到停止后的坑位中
有没有发现挖坑法是hoare的改版能避免我们去讨论一些细节更加易于理解。
//挖坑法
int PartSort2(int* a, int left, int right)
{int key a[left];int hole left;while (left right){while (left right a[right] key){right--;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
前后指针法
这种方法和前两种方法不同是一种全新的思路比较抽象但也是最简洁的一种写法。
主要思路
以最左边为基准值key设置prev和cur两个指针一前一后如果cur指向的值小于key则先prev再交换prev和cur指向的值最后cur如果cur指向的值大于等于key则cur最后cur越界循环停止将key和prev指向的值交换
分析 最开始prev和cur是相邻的 当cur遇到比key大的值则与prev分离开中间间隔的都是比key大的值 当cur找到比key小的值prev向后一格指向比key大的值再与cur交换相当于翻滚式的将比key大的值向右推同时把小的换到左边 最后cur越界时prev所在的值经过前面的交换肯定比key小所以与key交换则完成了左边全比key小右边全比key大的子序列分割。
这里代码实现时加上了额外判断使prev和cur相等时不进行交换
//前后指针法
int PartSort3(int* a, int left, int right)
{int keyi left;int prev left;int cur prev 1;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[keyi], a[prev]);return prev;
}上述三种思路只是实现方式的不同但是实际快速排序的效率是相等的。
运行结果 时间复杂度分析
O(N*log2N) — 最好和平均当每次选key为中位数时则最好 O(N2) — 最坏如果数据有序即每次选key最小或最大则最坏 那么我们如何尽可能避免最坏情况的发生呢这里就可以用一种方法进行优化——三数取中法
取头尾元素和中间元素相互比较选出大小处于中间的值返回其下标
int GetMidIndex(int* 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[right] a[left]){return left;}else{return right;}}else//a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[right] a[left]){return left;}else{return right;}}
}再将其与最左边key的位置交换尽量保证key不会是最大或者最小这里用前后指针法举例子 空间复杂度 — O(log2N)快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序
2.3.2.2 非递归实现
当然递归还有相应的缺陷就是当数据量太大时有栈溢出的风险。所以我们应该掌握一下非递归实现的方法——用栈模拟递归
因为栈是动态开辟在堆区的而堆区空间远远比栈区大基本没有溢出风险。
因为C语言没有对应的库所以我们将之前写好的栈拷贝过来。
主要思路
先创建栈并初始化将endbegin依次压栈因为栈是后进先出的所以想与之前递归的方式相似必须先把右边元素压栈才能先取左边元素进入循环依次取出最左边下标与最右边下标分割子序列并获取基准值下标keyi如果keyi 1 right则右区间存在将区间下标按先右后左的方式压入栈如果left keyi - 1则左区间存在将区间下标按先右后左的方式压入栈这样不断循环便模拟实现了递归的效果实际非递归的快速排序
运行结果 void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int keyi PartSort3(a, left, right);if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}if (left keyi - 1){STPush(st, keyi - 1);STPush(st, left);}}STDestroy(st);
}2.3.3 冒泡排序和快速排序的性能对比包括前面
既然冒泡排序和插入排序时间复杂度最坏都为O(N2)最好都为O(N)谁能更胜一筹呢还有刚刚实现的快速排序比起希尔排序堆排序是否能力压群雄呢请看下面测试release版本。
数据量为10w时
数据随机无序 数据有序 我们可以发现同为O(N2)量级的插入排序选择排序和冒泡排序中插入排序对数据适应性最强综合最优而冒泡排序虽然在数据随机无序比选择排序略低但是在数据接近有序或有序的情况下也有较强的适应性但是选择排序却对数据没有任何适应性。
O(N2)插入排序 冒泡排序 选择排序
数据量为100w时
因为冒泡排序和选择排序太慢了所以这里它们将退出舞台。
数据随机无序 数据有序 我们发现在100w数据量下插入排序已经非常吃力在数据无序随机的情况下快速排序确实更优一些而在数据有序的情况下插入排序以及其进阶的希尔排序对数据有序或接近有序有着天然的极强适应性因为插入排序的思想便是插入已经有序的数组
数据量为1000w时
这时插入排序也更不上时代的步伐了必须退居二线。 数据量为1亿时
让我们再疯狂一点吧 这时我们居然发现快速排序效率居然急剧下降这是为什么呢 其实快速排序还有一个致命的弱点——无法快速处理含有大量相同元素的数据而我们产生的随机数是有范围的0—3w所以总数据量非常大的情况下数据中就会产生大量相同元素。那怎么解决呢请看下面优化。
2.3.4 快速排序优化
分析当数据中含有大量重复元素时我们的三数取中法就会失效因为取出的三数极有可能相等。这样我们又会面临最坏情况快速排序将会退化成冒泡排序。
优化思路
原本我们的思路是两路划分小于等于key的放左边大于等于key的放右边 但是之前的思路并没有对等于key的值有很好的处理所以才会留下这个“死穴”。那么我们转换新思路——三路划分将等于key的值放在中间这样就完美解决了这个问题。 具体方法
设置leftcurright三个指针如果a[cur] keycur和left交换leftcur如果a[cur] keycur和right交换right–如果a[cur] keycur
看图分析
假设key6则left在最左边cur在left右边一格right在最右边 a[cur] keycur和left交换leftcur a[cur] keycur a[cur] keycur和right交换right– a[cur] keycur和right交换right–a[cur] keycur a[cur] keycur和right交换right– a[cur] keycur和left交换leftcura[cur] keycur a[cur] keycur和left交换leftcur 循环条件cur right
这样经过上图的分析是不是很清晰地理解了该优化算法的运作其实我们可以发现该方法是hoare版本左右指针法和前后指针法的结合体取二者之精华。
进一步理解left 和 right 最后锁定了值全为key的区间。
递归的子区间划分[begin, left - 1] [left, right] [right 1, end]
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int left begin;int right end;int cur left 1;int mid GetMidIndex(a, left, right);Swap(a[left], a[mid]);int key a[left];while (cur right){if (a[cur] key){Swap(a[cur], a[left]);}else if (a[cur] key){Swap(a[cur], a[right--]);}else{cur;}}QuickSort(a, begin, left - 1);QuickSort(a, right 1, end);
}最后我们再更改一下三数取中法让其不再固定取中而是随机取中。 再来测试1亿的数据量 我们发现快速排序又遥遥领先啦
优化后的三路划分的快速排序效率有略微地下降因为判断的次数变多但是使用的场景更加普遍和广泛
2.4 归并排序
基本思想归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 2.4.1 递归实现
归并排序首先需要动态开辟n个元素大小的tmp空间因为空间只用开一次所以不能在本函数内进行递归那么就写一个子函数进行递归调用。
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}归并排序递归的思路和二叉树后序遍历规则十分相似也是利用二叉树结构的排序。 返回条件当区间长度为0时则返回为0代表一个元素同时区间不可能不存在子问题转换为 [begin, mid] [mid 1, end] 两个区间进行归并因为归并要两边为有序区间所以一直递归到一个元素时便两两归并归并逻辑两有序区间从头比较取小的尾插tmp数组。如果一边区间取完则代表另一区间中剩余的数均大于之前的数则直接追加到tmp后面即可。最后将tmp数组中的归并好的元素拷贝回原数组对应位置。
运行结果 时间复杂度O(N*log2N)空间复杂度O(N)
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end){return;}int mid (begin end) / 2;int begin1 begin, end1 mid;int begin2 mid 1, end2 end;_MergeSort(a, begin1, end1, tmp);_MergeSort(a, begin2, end2, tmp);int i 0;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, sizeof(int) * i);
}2.4.2 非递归实现
大体思路
将数据分组归并总共gap组gap初始为1每一轮循环gap * 2循环内每组进行归并排序并拷贝回原数组
gap1时 一组归并拷贝完则起始位置gap进行第二组……直到将所有元素两两归并拷贝回原数组 gap2时 gap4时 void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);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 0;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, sizeof(int) * j);}gap * 2;}free(tmp);
}但是我们发现上述代码只有在2的次方数个数据才有用其他个数时比如10个就会程序崩溃或者随机值这是为什么呢其实这是因为数组访问越界让我们打印出边界值来分析一下。 经过分析这里一共有三种情况的越界。
情况一end1begin2end2全部越界 情况二begin2end2越界 情况三end2越界 所以针对以上情况我们要进行修正。
对于情况一和情况二我们直接break跳出循环不用对单个区间归并因为本身已经有序对于情况三我们将end2边界值修正到n-1即可 正确的运行结果 void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);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;if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}int j 0;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, sizeof(int) * j);}gap * 2;}free(tmp);
}2.4.3 归并排序优化
其实我们发现当区间长度比较小时可以不用归并排序而用其他排序则能更快完成数据的排序。而从基本排序里选择插入排序便是我们的首选。这种优化方式称为小区间优化
当区间长度小于10时我们便使用插入排序辅助完成归并。 有人可能会疑惑觉得区间长度怎么才小于10如果再大一点不是排序的更快速吗
其实小于10的不采用归并递归减少了最后三层的递归调用。如下图 而根据二叉树的性质我们知道最后三层加起来便占用了 87.5%的递归调用次数所以小区间优化实际上已经减少了绝大部分递归次数区间长度继续扩大减少次数却微乎其微了 实际上小区间优化也能用在快速排序上不过值得注意的是小区间优化只是锦上添花并不能起决定性的改变作用。
测试1亿的数据量 归并排序是不是快了不少
2.4.4 归并排序的应用——外排序
归并排序主要思考的是解决硬盘中的外排序问题。
之前我们讲的所有排序都可以解决在内存中的排序问题这种称为内排序。而归并排序不仅能用于内排序还能用于外排序。
那么为什么要使用外排序呢让我们来思考一个问题如果要对100亿个整数进行排序应该怎么办要知道100亿整数就是400亿字节换算过来大约是40G而你的内存显然没有那么大
这个时候我们就只能在硬盘中进行数据排序。而在硬盘中有一个致命的缺陷那就是文件只能顺序读取不支持下标随机访问。这才导致之前的种种排序算法都无能为力而只有归并排序的非递归可以做到按顺序从小到大依次归并。 这里简单介绍一下外排序后期会专门讲解归并排序怎样对文件进行外排序
三、排序算法复杂度及稳定性分析 3.1 稳定性的意义
简单来说稳定性是指排序完后相同元素相对位置不变。
那么稳定性有什么意义呢
假设考试要选前三名但是有4个分数相同的那么先交卷的排名就高。所以这时候就需要稳定的排序算法来完成分数的排序保证排序完先后交卷的顺序不变。 3.2 稳定性分析
直接插入排序稳定希尔排序不稳定因为相同元素可能分在不同的组直接选择排序不稳定堆排序不稳定冒泡排序稳定快速排序不稳定归并排序稳定
3.3 排序算法时间、空间复杂度和稳定性比较表格
排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(N2)O(N)O(N2)O(1)稳定直接选择排序O(N2)O(N2)O(N2)O(1)不稳定直接插入排序O(N2)O(N)O(N2)O(1)稳定希尔排序O(N) ~ O(N*log2N)O(N1.3)O(N2)O(1)不稳定堆排序O(N*log2N)O(N*log2N)O(N*log2N)O(1)不稳定归并排序O(N*log2N)O(N*log2N)O(N*log2N)O(N)稳定快速排序O(N*log2N)O(N*log2N)O(N2)O(log2N) ~ O(N)不稳定
看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注 ❤️ 拜托拜托这个真的很重要 你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includesort.hvoid TestInsertSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);InsertSort(a, sz);PrintArray(a, sz);
}void TestShellSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);ShellSort(a, sz);PrintArray(a, sz);
}void TestSelectSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);SelectSort(a, sz);PrintArray(a, sz);
}void TestHeapSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);HeapSort(a, sz);PrintArray(a, sz);
}void TestBubbleSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);BubbleSort(a, sz);PrintArray(a, sz);
}void TestQuickSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);QuickSort(a, 0, sz-1);//QuickSortNonR(a, 0, sz - 1);PrintArray(a, sz);
}void TestMergeSort()
{int a[] { 5,9,8,4,6,3,1,5,6,4,8 };int sz sizeof(a) / sizeof(a[0]);PrintArray(a, sz);MergeSort(a, sz);//MergeSortNonR(a, sz);PrintArray(a, sz);
}void TestOP()
{srand((unsigned int)time(NULL));const int N 100000000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];}int begin1 clock();//InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();//SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();//BubbleSort(a5, N);int end5 clock();int begin6 clock();QuickSort(a6, 0, N-1);int end6 clock();int begin7 clock();MergeSort(a7, N);int end7 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(BubbleSort:%d\n, end5 - begin5);printf(QuickSort:%d\n, end6 - begin6);printf(MergeSort:%d\n, end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{srand((unsigned int)time(NULL));//TestInsertSort();//TestShellSort();//TestSelectSort();//TestHeapSort();//TestBubbleSort();//TestQuickSort();//TestMergeSort();TestOP();return 0;
}
