前端开发培训机构tuj,seo专员是什么职业,郑州网站建设公司哪家专业好,WordPress封面生成#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负 目录
前言
1.冒泡排序
2.快速排序
2.1Hoare版
2.2占…
樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》
每一个不曾起舞的日子都是对生命的辜负 目录
前言
1.冒泡排序
2.快速排序
2.1Hoare版
2.2占坑版
2.3前后指针版
2.4三数取中对快速排序的优化
2.5非递归版
3.归并排序
3.1递归版
3.2非递归版
3.3外排序问题
4.计数排序 前言
本篇文章博主将继续带来排序算法实现主要讲解交换排序思想中的冒泡排序、三种快速排序递归版和一种非递归版归并排序中的递归版和非递归版以及计数排序的相关内容。 欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码fanfei_c的仓库 1.冒泡排序
冒泡排序顾名思义整个排序的过程就像泡泡不断上升以升序为例较大的数值会与较小的数值交换每趟排序都可以将一个数放到合适的位置比如最大值在最后次大值放倒数第二个位置等。 图片取自GITHUB-Olivier Wietrich 所以我们需要双层循环控制。
在遍历整个序列的同时内部的单趟排序要每次都减少一次比较因为每趟排序都有一个元素到了合适的位置就需要将这个元素剔除掉下次的排序中也同样的我们就可以知道外层循环需要执行n次才能让所有的元素放置在正确的位置上。
冒泡排序的特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
代码实现
// 冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n ; i){int flag 0;for (int j 1; j n - i; j)//每次减少一个需要排序的元素{if (a[j-1] a[j]){swap(a[j], a[j - 1]);flag 1;}}if (flag 0){break;}}
} 2.快速排序 快速排序算法是由东尼·霍尔设计提出接下来我会为大家讲解一下快排的霍尔版以及后面各路大佬对快排的优化优化再优化。 快排的特性总结我放到快速排序部分最后罗列。
2.1Hoare版
Hoare版的思想不容易理解。
首先无论哪种版本的快排核心思想都是任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值可以理解为二叉树的结构然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
那么我们如何进行操作呢
单趟排序的思想
以第一躺排序为例先不考虑后面的递归首先将待排序序列最左端的元素设定为我们首躺排序中需要找到合适位置的根代码中备注三数取中的地方大家可以先不用管先掌握思路后面会讲。 int keyileft。 我们知道左指针left此时在最左端右指针right此时在最右端我们令右边先走必须右边先走才能保证left与right相遇的点小于根keyi的点这个后面也会讲大家先往后捋思路当右指针right指向小于根的点时停下来同样的当左指针left指向大于根的点时停下来然后交换他们所指向的元素此时是不是left指向的元素也小于根了right同理。 while (left right a[right] a[keyi]) { right--; } while (left right a[left] a[keyi]) { left; } swap(a[left], a[right]); 也就是说我们可以通过这样的操作来实现left左边的值都小于根right右边的值都大于根当left与right相遇时由于相遇点必然小于根所以我们交换根指向的元素与相遇点指向的元素此时就完成了一趟排序也成功实现了我们上面需要完成的功能。
递归的思想
我们每一趟排序都可以将一个元素放在正确的位置并且该元素左面的值都小于它右面的值都大于它那么我们就可以以该元素为分割点他左面的序列执行单趟排序的算法右面的序列同样要执行单趟排序的算法。 但是其实递归到后面有很大程度的浪费比如二叉树的最后一层占据了整个二叉树节点数的50%倒数第二层25% ……我们发现在后面的排序中其实递归是存在很大程度浪费的所以我们可以在末尾几层不递归了直接采用插入排序。 if ((end - begin 1) 10)
{……;
}
else
{InsertSort(a begin, end - begin 1);
}
其实在Release版本下影响并不大因为编译器已经将递归的代价优化的很小了。 但这何必不是一种优化的手段面试的时候可能会有用噢 大家有没有发现这就是二叉树中前序遍历的思想先搞定根的位置然后处理左子树再处理右子树不同的是我们只需控制左子树的下标范围和右子树的下标范围罢了。 图片取自wikipedia-Quicksort 那么为什么右边先走就能保证相遇点一定小于keyi点呢
相遇之前最后一次挪动的指针如果为右指针代表左指针刚刚遇到大于keyi点的值并完成了交换然后新一轮循环右指针先走那么右指针right停下来的位置必然就是此时刚刚交换完值的左指针的位置而我们知道左指针此时指向的值一定小于keyi点。相遇之前最后一次挪动的指针如果为左指针代表右指针刚刚遇到小于keyi点的值左指针此时向右走与右指针相遇所以相遇点此时的值一定小于keyi点。
代码实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int midi GetMidi(a, left, right);//三数取中后面会讲swap(a[midi], a[left]);int keyi left;while (left right){//右边先走确保left与right相遇在小于key的点while (left right a[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}swap(a[left], a[right]);//此时left的内容大于right的内容交换两者}swap(a[left], a[keyi]);//将keyi的内容放到left与right的相遇点return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;// 小区间优化小区间不再递归分割排序降低递归次数if ((end - begin 1) 10){int keyi PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}
} 2.2占坑版
核心思路不变单趟排序的思想有所调整。
思路
首先先将第一个数据存放在key中形成第一个坑位。 int key a[left]; int hole left; 因为你的key首个取值在最左面即坑位在最左面所以找下一个坑位的位置应该从右面开始当右指针指向的元素小于key时形成新的坑位再从左面开始找当左指针指向的元素大于key时形成新的坑位重复这一过程 while(leftright) { while (leftright a[right] key) { right--; } a[hole]a[right]; hole right; while (leftright a[left] key) { left; } a[hole] a[left]; hole left; } 直到左右指针相遇相遇时我们把最开始保存的key值放到坑位中返回坑的位置。 a[hole] key; return hole; TIP递归思想和Hoare版是一样的。
代码实现
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);swap(a[midi], a[left]);int key a[left];int hole left;while (left right){while (leftright a[right] key){right--;}a[hole]a[right];hole right;while (leftright a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;// 小区间优化小区间不再递归分割排序降低递归次数if ((end - begin 1) 10){int keyi PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}
} 2.3前后指针版
前后指针版的思想更加简单他定义了两个指针一个指针在前指向left一个指针在后一个位置left1并且保存left此时的位置因为left后面会移动走 int prev left; int cur left1; int keyi left; 当cur指向的内容小于keyi指向的内容就交换prev1指向的元素与cur指向的元素不能交换prev位置因为prev首次在left位置而left位置也就是keyi的位置的元素是重要的参照条件要在最后交换不管cur指向的元素小于或者大于等于keyi指向的元素cur都向后移动循环这个过程直到cur超过right while (cur right) { //cur指针指向的内容小于key时交换prev指针和cur指针指向的内容 //因为要交换的是prev的下一个所以要加这个判断如果prev1的位置等于cur的位置时就不要交换了 if (a[cur] a[keyi] prev!cur) { swap(a[prev], a[cur]); } cur; //不管大于小于cur前进都一格 } 最后将参照值与prev交换返回该位置。 swap(a[prev], a[keyi]); return prev; 本质上可以理解为把大于key的一段区间推箱子似的往右推并把小的甩到左面去。
代码实现
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);swap(a[midi], a[left]);int prev left;int cur left1;int keyi left;while (curright){if(a[cur] a[keyi]){swap(a[prev],a[cur]);//这里相当于prev1的位置等于cur的位置时也交换浪费资源}cur;}swap(a[prev], a[keyi]);return prev;
}// 快速排序前后指针法(优化版)
int PartSort3_1(int* a, int left, int right)
{int midi GetMidi(a, left, right);swap(a[midi], a[left]);int prev left;int cur left 1;int keyi left;while (cur right){//cur指针指向的内容小于key时交换prev指针和cur指针指向的内容//因为要交换的是prev的下一个所以要加这个判断如果prev1的位置等于cur的位置时就不要交换了if (a[cur] a[keyi] prev!cur){swap(a[prev], a[cur]);}cur; //不管大于小于cur前进都一格}swap(a[prev], a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;// 小区间优化小区间不再递归分割排序降低递归次数if ((end - begin 1) 10){int keyi PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}
} 2.4三数取中对快速排序的优化
这就是上面所有快排方法中都用到的一个排序前的操作那么为什么要加这一段操作呢
我们直到快排是一种极为有效的排序方法但当他遇到较为有序的序列进行排序时或者极端一点当他排已经有序的一段序列时他的时间复杂度是O(N^2)每趟排序时间复杂度量级为N需要N趟。
因为有序所以他每次选取的根都在一侧而不是最理想的中间位置也就是说这棵递归二叉树严重偏离。 图 理想情况与最差情况的对比 那么怎么办呢
我们只需要利用三数取中避免每次都取到最小的值或最大的值作为坑位参照值 对比序列两侧和中间值取中间大小的那个值与left指向的内容交换即可。
代码实现
//三数取中
//三数取中对于已经有序的序列使用快速排序有很好的优化作用
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[mid] a[left]){if (a[mid] a[right]){return mid;}else if(a[left]a[right]){return left;}else{return right;}}else//a[mid]a[left]{if (a[right] a[left]){return left;}else if(a[right]a[left] a[right]a[mid]){return mid;}else{return right;}}
}2.5非递归版
非递归方式实现快排可以采用栈的数据结构也可以采用队列的数据结构辅助完成。
比如用栈的数据结构进行实现。
代码实现
// 快速排序 非递归实现
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 PartSort3_1(a, begin, end);if (keyi1end)//将右半序列压栈{STPush(st, end);STPush(st, keyi 1);}if (beginkeyi-1)//将左半序列压栈{STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st);
} 快速排序的特性总结
快速排序整体的综合性能和使用场景都是比较好的时间复杂度O(N^logN) //在使用三数取中优化后空间复杂度O(logN)稳定性不稳定 3.归并排序
归并排序的核心思路
将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。 归并排序的特性总结我放到归并排序部分最后罗列。
3.1递归版
在递归版中依照归并排序的核心思路我们需要先将子序列有序再最后合并子序列那么很容易会联想到二叉树部分的后序遍历思想即先解决左右子树最后解决根。 回归到排序中就是先将整个待排序序列拆分成N多个子序列左右子树然后将子序列根进行排序操作即可。 现在我们需要解决的就只是如何将子序列进行排序的问题了。
子序列排序
我们可以创建一个临时数组将子序列再拆分想象为两段在这两段上分别定义左右指针右指针用来标记结束位置左指针依次与另一端左指针比较大小假设排升序那我们就将小的那一段先放到临时数组中依此类推如果有一段先结束了左指针超过右指针那么证明另一段序列剩下的数据都大于该段序列此时左指针指向的值所以直接追加到临时数据即可最后再将排好序的临时数组拷贝回原数组即可。
代码实现
//归并排序子函数
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end begin){return;}int mid (begin end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);//后序思想int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int inrex begin;while (begin1end1 begin2 end2){if(a[begin1] a[begin2])//这里如果为那么该排序方法就为不稳定的tmp[inrex] a[begin1];elsetmp[inrex] a[begin2];}//如果两段比较序列中的任意一段有剩余//说明该段序列剩下的数据都大于或都小于另一段序列的某个值//则将该段直接追加给tmp数组中即可while (begin1 end1){tmp[inrex] a[begin1];}while (begin2 end2){tmp[inrex] a[begin2];}//最后将排好序的tmp数组拷贝到a数组中memcpy(abegin, tmpbegin, (end - begin 1)*sizeof(int));
}// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(n*sizeof(int));if (tmp NULL){perror(malloc fail);exit(-1);}_MergeSort(a, tmp, 0, n - 1);return;
} 3.2非递归版
非递归版的思想是先将整个序列划分为N多个子序列然后将这些子序列两两进行比较排序后放到临时数组执行完一遍将子序列减少一半代码中是利用gap实现这个思路再重复这一过程。
但非递归有一个很容易出现的问题数组越界访问。
我们每次执行完一遍后是利用gap*2实现的减少一半子序列可是每次gap变为之前的二倍的时候由于begin和end的取值就是依据gap来定义的。 比如end2i2*gap-1 想一想是不是很容易越界
那么我们如何解决这一问题呢 图 越界的情况分析 if (begin2 n)//包含了上图中提到的前三种情况直接break { break; } if (end2 n)//到这说明begin2未越界end2越界将end2重新修正 { end2 n - 1; }
代码实现
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(n * sizeof(int));if (tmp NULL){perror(malloc fail);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2*gap){int begin1 i;int end1 i gap-1;int begin2 i gap;int end2 i 2 * gap - 1;int inrex i;//如果begin2已经越界则直接跳过本次归并if (begin2 n){break;}if (end2 n)//到这说明begin2未越界end2越界将end2重新修正{end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])//这里如果为那么该排序方法就是不稳定的tmp[inrex] a[begin1];elsetmp[inrex] a[begin2];}while (begin1 end1){tmp[inrex] a[begin1];}while (begin2 end2){tmp[inrex] a[begin2];}//将本次归并结果拷贝回a数组memcpy(a i, tmp i, (end2-i1)* sizeof(int));//这里的第三个参数也是避免越界的重要因素}gap * 2;}free(tmp);return;
} 归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 3.3外排序问题
前面讲到的所有排序方法都是内排序就是在内存中排序的方法。 那么他们能不能对磁盘中的数据进行排序呢 答案是不能注意磁盘中不支持下标随机访问一般在磁盘中都是顺序写顺序读。 你可能有使用fseek调整文件指针的想法可是那样效率极差。
而归并排序的思想却可以帮助我们实现外排序即在磁盘中进行排序。
比如现在有一个4G大小的数据文件要求你对该文件进行排序操作。
依据归并排序的思想我们就可以将他先切分成几4份新文件大小1G每份新文件就可以读取到内存中利用内排序的方法进行排序然后将这几段有序的新文件用文件指针打开利用归并思想比较然后覆盖写入可以放下两段序列的新文件重复这一过程直到覆盖写入原4G大小的文件中。 4.计数排序
计数排序的思想就是先统计出相同数据出现的次数然后根据他们出现的次数将序列回收到原来的序列中。
简单点就是
先求出待排序序列最大最小值从而得到待排序序列取值的范围然后创建一个这么大范围的计数数组之后再遍历原数组谁出现了就在谁的计数数组位置上1可以得到每个元素出现的次数最后再根据他们出现的次数依次放回。 虽然看着很傻瓜式的方法但是大家不妨观察下代码实现部分其实设计逻辑非常巧妙我已经在源代码中注释出来了 大家可以学习下。 相信大家缕清计数排序的思路后就会发现他适合数据非常紧凑的数据排序并且在很多情况下他的时间复杂度非常低。 图 数据量1e6的情况下各排序速度比较单位ms 代码实现
// 计数排序
void CountSort(int* a, int n)
{int max a[0];int min a[0];for (int i 0; 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);if (count NULL){perror(malloc fail);exit(-1);}memset(count, 0, sizeof(int) * range);统计出现数据次数普通思路//for (int i 0; i range; i)//{// for (int j 0; j range; j)// {// if (count[i] a[j])// count[i];// }//}//统计出现数据次数非常巧妙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,范围))空间复杂度O(范围)稳定性稳定 截至到这里博主现阶段对于排序的内容就结束啦
那么你是否有所收获呢
排序的思想学习很重要只要你掌握了这种排序思想那么代码实现就只是时间的问题了 如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
