建设网站利用点击量赚钱,聊城做网站的公司平台,全球十大搜索引擎排名,红酒手机网站模板文章目录前言排序算法插入排序直接插入排序:希尔排序(缩小增量排序)选择排序直接选择排序堆排序交换排序冒泡排序快速排序hoare版本挖坑法前后指针版本快速排序的非递归快速排序总结归并排序归并排序的非递归实现#xff1a;计数排序排序算法复杂度及稳定性分析总结前言
本篇…
文章目录前言排序算法插入排序直接插入排序:希尔排序(缩小增量排序)选择排序直接选择排序堆排序交换排序冒泡排序快速排序hoare版本挖坑法前后指针版本快速排序的非递归快速排序总结归并排序归并排序的非递归实现计数排序排序算法复杂度及稳定性分析总结前言
本篇将讲述常用的排序算法包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序使用动图解释并且画图阐明了递归的写法同时实现了与非递归的写法复杂度和稳定性分析等等看完绝对不亏 作者 迷茫的启明星 欢迎关注点赞收藏✍️留言 家人们码字不易你的点赞收藏❤️关注对我真的很重要有问题可在评论区提出感谢阅读 持续更新中~
排序算法
排序的概念及其运用 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 全文以升序为例降序类似 常见排序 插入排序 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 直接插入排序: 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 其实就是将前面i个数视为一个有序数组即使是一个也是有序数组第i1的数和前一个数比较如果比它小就不变比它大就让大的数往后移一直到遇到比它小的数为止。这里指的是升序。 直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
代码实现
void InsertSort(int* a, int n)
{for (int i 0; i n-1; i) {int endi;int xa[i1];while(a[end]xend0){a[end1]a[end];end--;}a[end1]x;}
}希尔排序(缩小增量排序) 希尔排序法又称缩小增量法。 希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有记录分成个组 所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。 然后gap不断取小重复上述分组和排序的工作。 当到达1时所有记录在统一组内排好序。 希尔排序的特性总结 希尔排序是对直接插入排序的优化。 当gap 1时都是预排序目的是让数组更接近于有序。 当gap 1时数组已经接近有序的了再让gap等于1以后 就是前面未优化的直接插入排序方式排序一次这样就会很快。 这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 稳定性不稳定 代码实现 void ShellSort(int* a, int n)
{int gapn;while(gap1){//gapgap/2;//shell的方式gapgap/31;//knuth的方式for (int i 0; i n-gap; i) {//多次预排序最后一次gap1直接插入排序//预排序使得数组更加有序后面直接排序便可加快效率int endi;int xa[igap];while(a[end]xend0){a[endgap]a[end];end-gap;}a[endgap]x;}}
}选择排序
基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素
存放在序列的起始位置直到全部待排序的数据元素排完 。
直接选择排序 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤 直到集合剩余1个元素 也就是说每次遍历都选出最大或者最小的值放到一端这样到最后就是有序的了。 直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 代码实现 void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin; i end; i){if (a[i] a[mini])mini i;if (a[i] a[maxi])maxi i;}Swap(a[begin], a[mini]);// begin maxi时最大被换走了修正一下maxi的位置if (begin maxi)maxi mini;Swap(a[end], a[maxi]);begin;--end;}
}这个排序整体来说是最差的排序方式因为无论什么情况都是时间复杂度O(N2) 堆排序 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 前面我们讲述二叉树的时候就已经讲过这个排序方式了 链接http://t.csdn.cn/LcTKm 直接选择排序的特性总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 skills: 在这里建堆最好使用向下调整来建堆如果使用向上调整来建堆 建堆的时间复杂度就要O(N*logN),而向下调整时间复杂度为O(N) 这些都在http://t.csdn.cn/LcTKm讲过了。 交换排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
冒泡排序 冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序时间复杂度O(N2)空间复杂度O(1)稳定性稳定 简单来说冒泡排序就是在[0,n-1]两两对比选出最大值放到a[n-1] 再从[0,n-2]先选出最大值放到a[n-2],如此循环下去就排好序了。 冒泡排序最好的情况是数组本就是有序此时经过一轮遍历后 没有发生交换就可以判断是有序数组了最好情况的时间复杂度为O(N), 但是一般情况不会是这样仍需要一个个选出最大值时间复杂度为O(N2). 代码实现 void BubbleSort(int* a, int n)
{int end n;while (end 0){int exchange 0;for (int i 1; i end; i){if (a[i - 1] a[i]){exchange 1;Swap(a[i - 1], a[i]);}}--end;if (exchange 0){break;}}
}快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法 其基本思想为任取待排序元素序列中的某元素作为基准值 按照该排序码将待排序集合分割成两子序列 左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值 然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 // 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div-1] 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div—1);// 递归排[div1, right)QuickSort(array, div1, right);
}我们会发现这很像二叉树的前序遍历只不过要注意基准值的改变以及边界的改变。 将其划分左右两部分的方式主要有两种
hoare版本 思路 取最左边的值为keyi然后R往左走找到比a[keyi]小的值就停 L往右走找到比a[keyi]大的值就停然后交换两个值 继续循环直到二者相遇值为x把a[keyi]与a[x]交换 自此keyi左边的值比a[keyi]小keyi右边的值比a[keyi]大 代码实现 int Partion1(int* a, int left, int right)
{int keyileft;while(leftright){while(a[keyi]a[right]leftright)right--;while (a[keyi]a[left]leftright)left;Swap(a[left],a[right]);}Swap(a[keyi],a[left]);return left;
}挖坑法 思路 与上面的思路相似取最左边的值为keyi 把a[keyi]备份试想左边这个为坑 然后R往左走找到比a[keyi]小的值就把它放到坑中 然后L往右走找到比a[keyi]大的值就把它放到坑中 继续循环直到二者相遇值为x把备份的a[keyi]放到坑中 自此keyi左边的值比a[keyi]小keyi右边的值比a[keyi]大 代码实现 int Partion2(int* a, int left, int right)
{int key a[left];int pivot left;while (left right){// 右边找小, 放到左边的坑里面while (left right a[right] key){--right;}a[pivot] a[right];pivot right;// 左边找大放到右边的坑里面while (left right a[left] key){left;}a[pivot] a[left];pivot left;}a[pivot] key;return pivot;
}前后指针版本 思路 设置最左值为key再设置两个指针一个在前为cur一个在后为prev。 cur从第二个开始prev从第一个开始在前的cur开始往前寻找比key小的值。 找到就停下来和prev1位置的值交换因为cur位置的值肯定比key大 而prev最初的位置是key所以最后prev所在的位置的值必然是比key小的。 停止的条件是什么呢是cur指针超出了数组范围。 就这样prev最后所在位置的值与key交换这样就实现了key左边比key小key右边比key大。 代码实现 int Partion3(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)//这个地方就比较巧妙把prev放在这里//为什么要判断prev不等于cur呢因为二者相同就没有交换的价值。{Swap(a[cur], a[prev]);}cur;}Swap(a[prev], a[keyi]);return prev;
}快速排序优化
三数取中法选key 三数指的是a[0],a[(n-1)/2],a[n-1],由于a[key]的值是无法预料它的相对大小的 当想要排升序时如果是倒序有序的话就是最坏的情况 这时如果取首尾中间值为key则变成了最好的情况 代码实现 int GetMidIndex(int* a, int left, int right)
{int middlleft(right-left)/2;if(leftmiddl){if(rightleft)return left;else if(rightmiddl)return middl;elsereturn right;}else//leftmiddl{if(rightmiddl)return middl;else if(rightleft)return left;elsereturn right;}
}这个函数可以放在上述所说的三种方法中只需向其中加以下代码 int mini GetMidIndex(a, left, right);
Swap(a[mini], a[left]);递归到小的子区间时可以考虑使用插入排序 递归可以想象成满二叉树的结构越到后面需要递归的次数越多这样 就使我们萌生一个想法把后面几次的递归排序换成直接插入排序。 想法是好的那么怎么实现呢 这时候就要考虑最后是什么情况了我们需要它数组递归到个数少的时 候就使用直接插入排序代码如下 void QuickSort(int* a, int left, int right)
{if (left right)return;// 小区间优化当分割到小区间时不再用递归分割思路让这段子区间有序// 对于递归快排减少递归次数if (right - left 1 10){InsertSort(a left, right - left 1);}//要注意这里插入排序的左值是数组开始的位置//右值是需要排序的个数参考上文讲述的插入排序函数的描述。else{int keyi Partion3(a, left, right);// [left, keyi-1] keyi [keyi1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}
}就这样我们实现了快速排序的递归实现方法最主要的是怎么确定key值 并且使key左边和右边比key小或者大最后使用递归的方式 一层层缩小数组使其有序最后整个数组有序那么非递归怎么写呢?
快速排序的非递归 在这里我们需要用到一个数据结构----栈 栈的实现我们之前在这里讲过这里直接使用它的代码就好 栈的实现链接http://t.csdn.cn/cZzJh 怎么使用 思路是这样的 首先将原数组的首末位置按照末先首后的顺序传入栈中 栈的作用主要是记录边界然后原数组按照上文讲过的让左边右边 比key大或者小的方法把key放到合适的位置然后把栈内的已经找到 key合适位置的边界删掉之后把key1和end的值传入栈 begin和key-1的值传入栈把这个边界里key放到合适的位置就删掉边界 继续传入key右边的边界和左边的边界 到了最后第一次的key前面的都有序了 这时开始key后面的边界开始按照前面所说的 开始把key放到合适的位置最后栈空了就结束了。 代码实现 这里我们就只把所用到栈的函数拿出来如果需要复现的可以到http://t.csdn.cn/cZzJh里把Stack.c和Stack.h文件复制放到源文件下。 void QuickSortNonR(int* a, int left, int right)
{ST st;StackInit(st);StackPush(st, left);StackPush(st, right);while (!StackEmpty(st)){int end StackTop(st);StackPop(st);int begin StackTop(st);StackPop(st);int keyi Partion3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]if (keyi 1 end){StackPush(st, keyi1);StackPush(st, end);}if (begin keyi-1){StackPush(st, begin);StackPush(st, keyi-1);}}StackDestroy(st);
}快速排序总结 在大部分场景下快速排序的性能都是比较好的所以才叫快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定
归并排序 基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法Divide and Conquer的一个非常典型的应用。 将已有序的子序列合并得到完全有序的序列 即先使每个子序列有序再使子序列段间有序。 若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 思路 开辟一个新数组存重新排序的结果原数组不断分半到最后只剩一个元素再开始归并两数比较小的放前面大的放后面这一块就有序了随着数组变大数变多依旧如此大的放前面小的放后面一个数组没有数了就把另一个数组没有放的值按顺序放在后面即可。 图示 由于代码过长不方便图示故中间比较大小的就省去了仅示例部分后面类似 代码实现 void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right){return;}int mid (left right) / 2;// [left, mid] [mid1, right] 有序_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);int begin1 left, end1 mid;int begin2 mid1, end2 right;int i left;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];}// tmp 数组拷贝回afor (int j left; j right; j){a[j] tmp[j];}
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);if (tmp NULL){printf(malloc fail\n);exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp NULL;
}这就是归并排序的递归实现其实还有一种非递归方法 但是并不推荐使用主要是使用时容易出错 数组边界容易出问题 但是还是在这里讲一下 归并排序的非递归实现 通过观察数组可以发现我们递归方法中分割的最后一步 把数组分成一个个单独的元素 但是数组里面我们可以把它看作是单个的元素 直接就是分的最后一步开始归并就好了 那么该怎么归并呢 这里我们就要设置一个变量gap来控制一次是几个元素进行归并 这一步是最主要的难点然后就是这几个数进行归并 到了后面数不够了怎么办比如说现在是八个数 先一一归然后两两归最后四四归这是理想情况 但如果是九个数呢最后还多了一个数怎么办 多的数和后面的归就越界了排序结果肯定就不对了 这里所说的就是边界控制问题了 基于我的代码循环情况越界情况有两种 前一个右边界就越界或者后一个的左边界就越界那就不用再继续了说明数组比较完了后一个右边界越界那就把它右边界设置为原来整个数组的右边界即可 代码实现 void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);if (tmp NULL){printf(malloc fail\n);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){// [i,igap-1] [igap,i2*gap-1]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// 核心思想end1、begin2、end2都有可能越界// end1越界 或者 begin2 越界都不需要归并if (end1 n || begin2 n){break;}// end2 越界需要归并修正end2if (end2 n){end2 n- 1;}int index i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}// 把归并小区间拷贝回原数组for (int j i; j end2; j){a[j] tmp[j];}}gap * 2;}free(tmp);tmp NULL;
}归并排序的特性总结 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 计数排序 计数排序顾名思义使用计数的方式进行排序它是哈希直接定址法的变形应用。 步骤 统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 图示 这里有一个问题一定要从0开始吗 如果有一组数是这样的[1000,1111,1022,1073,1288],给它排序难道要浪费前面一千个空间来记录吗 当然不需要像这种集中在一定区域的数就把它最小的数放在0那其他的数就映射到x-min上与从0开始不同的是这是相对的映射而那是绝对映射。我们怎么确定要开辟多大的空间来存放数据呢循环一遍找出最大最小值即可1. 代码实现 void CountSort(int* 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;int* count (int*)malloc(sizeof(int)*range);memset(count, 0, sizeof(int)*range);if (count NULL){printf(malloc fail\n);exit(-1);}// 统计次数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;}}
}计数排序总结 因为计数排序的适用性不强故不在后面总结中提及此处仅作涉猎 在数据比较集中时效率很高但是适用范围和场景有限 如果范围较大或者是浮点数就不适用了。 时间复杂度O(max(N,range)) 空间复杂度O(范围) 稳定性稳定 排序算法复杂度及稳定性分析 算法复杂度分析前文已经讲述过了总结参考上图。 稳定性是什么呢 假定在待排序的记录序列中存在多个相同的关键字的记录若经过排序这些记录的相对次序保持不变就称这种算法是稳定的否则是不稳定的。 那么前面讲过的排序方式哪些是稳定的、哪些是不稳定的呢. 插入排序 直接插入排序稳定 希尔排序不稳定 在相同的值预排时可能分到不同的组里导致相对位置改变 选择排序 选择排序不稳定 如果有两个相同的数一个在首位这时如果最小的数在另一个的右边那么相对位置将会改变 堆排序不稳定 排升序时如果最小的数在末尾而最大数在前不止一个那么将最大的数替换后 最大数的相对1位置也会发生改变 交换排序 冒泡排序稳定 快速排序不稳定 有相同元素时相对位置可能会发生变化 归并排序 归并排序稳定 计数排序不稳定 归并时如果相同会先归左边的数这样会导致相对位置改变 总结
这一篇我们讲述了八大排序算法包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序并且进行了算法复杂度和稳定性的分析。可是知道理论和死板的重现是远远不够的还需要刷题来巩固主要掌握的是这种思想。
respect !
下篇见
