多种排序算法

一.插入排序。1.算法描述①.单趟的分析。整个序列区间为[0,n-1]。在某个单趟中设需要插入排序的元素下标为(end1)则在前面[0,end]的区间里所有元素有序。此时将要排序的元素抽出并用tmp储存因为end会不断变化随后判断tmp与a[end]的大小若tmp a[end]那么让end所指的元素向后挪一个位置即a[end1] a[end])然后end--。就这么循环往复一直到tmp a[end]为止此时将tmp插到a[end]后面a[end1] tmp。②.整体的分析。看完对单个元素的插入排序我们再来关注整个序列所有元素的插入排序。其实只需要配合一个for循环就好,即令end的初始值依次等于a的每一个下标i,随后i,即可实现每个元素的排序。但需要注意的是end1的初始值始终对应的是待排序数 。2.细小的坑。①.关于为什么是i n - 1的问题。首先下标的区间是[0,n-1]但为什么i无法取n-1呢因为在该算法中要插入的数据,即tmp所对应的下标始终是end1则需要对序列最后一个元素排序时其下标为end1,而end n - 2(即倒数第二个元素的下标)。同时在代码中我们始终让end每一趟初始值 i以实现for循环的遍历。所以在遍历最后一个元素时i n-2。②.关于else里不插入反而写break的问题。我们来讨论一个极端状况假如待排序数为全场最小end最终状态为-1而while的条件是end0。如果这个时候在else内执行插入操作就会导致跳出循环待排序数没法插入。3.代码的实现。void InsertSort(int* a, int n) {//整个序列区间为[0,n-1].[0,end]有序将end1所对应元素插入有序区间内。 for (int i 0; i n - 1; i)//因此处理整个序列最后一个元素的排序时end n-2,end1 n - 1,而i又对应着该趟end的初始值因此i n - 1。 { //单趟。 int end i; int tmp a[end 1];//找个值存储将被覆盖的end 1. while (end 0) { if (tmp a[end]) {//小于就挪大于就插。 a[end 1] a[end]; end--; } else { break;//将插入放在循环外是为了规避tmp在整个序列里最小且需要插入排序时end -1出循环从而没法插入的问题。 } } a[end 1] tmp; } }4.关于复杂度的讨论。最差即逆序的情况此时挪动次数为123...n-2即O(N^2)。最好即整个序列顺序的情况此时无需挪动只让i不断就行了为O(N)。二.希尔排序。1.算法描述。该排序主要对插入排序倒序所造成的费时进行优化分为两个部分①.预排序让数组先接近有序。将序列分成gap个组每组元素间间隔gap在遭遇逆序这种极端情况时大数可以一次挪动gap个位置而不像插排那样一次只能挪一个位置。最终序列然后在每一个组里进行插入排序,但一定要记得每次自加的数为gap而非1。最后整个序列相比起倒序更加有序也就更能减少时间。②.插入排序。(详情见一)在进行预排序以后将所得到的序列进行插入排序即可得到顺序的序列。2.算法实现。①.关于每次移动步数的问题。其每一组内的排序上其实依旧是插入排序只是待排序数(tmp)下标的所对应的是endgap的初始值毕竟每个元素之间间隔gap而非纯插排中的1。②.关于如何操控组数的问题。再在插排外面嵌套一个for循环循环走gap次即可同时令内层for循环中i的初始值为j。单个预排序代码实现void ShellSort(int* a, int n) { int gap 3; for (int j 0; j gap; j)//利用j来调控组数。 { for (size_t i j; i n - gap; i gap) { int end i; int tmp a[end gap]; while (end 0) { if (tmp a[end]) {//挪。 a[end gap] a[end]; end - gap; } else { break; } } a[end gap] tmp;//插。 } } }③.关于选gap的问题。上面部分的gap是锁死的但gap的大小会影响排序的效率且不同序列的gap也不尽相同所以我们接下来探讨一下gap取何值最合适。依据大gap和小gap的特点我们利用while循环与(gap/3) 1将二者结合,进行多次预排序gap每进行一次预排序缩小三分之一大gap保证速度小gap保证精度直至最后gap为1gap为1时进行插入排序。由此实现全部算法全部部分(预排序插入排序)。gap/3后加1可保证无论如何最终gap都能为1也就是最终都是插排。最终代码void ShellSort(int* a, int n) {//一组一组来。 int gap n; while (gap 1) {//进行多次预排序gap每进行一次预排序缩小三分之一大gap保证速度小gap保证精度直至最后gap为1gap为1时进行插入排序。由此实现全部算法。 gap gap / 3 1;//1使得无论如何最终gap都能为1。 for (int j 0; j gap; j)//利用j来调控组数。 { for (size_t i j; i n - gap; i gap) { int end i; int tmp a[end gap]; while (end 0) { if (tmp a[end]) {//挪。 a[end gap] a[end]; end - gap; } else { break; } } a[end gap] tmp;//插。 } } } }三.选择排序。1.算法描述。在序列里每遍历一遍选出最小的一个与该趟遍历初始的那个元素进行交换放到左边。优化一下既选最小也选最大。在begin与end区间内找到最小数放到最左边(begin)最大数放到最右边(end)。2.算法实现。单轮遍历①.找到每一轮遍历的最大最小值。先设置最大值下标为maxi最小值下标为mini。将它们初始值都假设为begin然后利用for循环对后面[begin 1,end]区间进行遍历如果满足a[i] a[maxi],将maxi的值换为i满足a[i] a[mini],将mini的值换为i。②.将每一轮遍历最大最小值放到相应位置。将已经找到的最大最小值利用Swap函数与begin或end进行交换使其到相应位置。整体利用while循环实现多次遍历每次遍历完以后记得end--,begin。void SelectSort(int* a, int n) { int begin 0; int end n-1; while (begin end)//begin到end间无序需要找最大最小值 {//最终大的在右小的在左。 //找最大最小值的下标 int mini begin; int maxi begin; for (int i begin 1; i end; i) { if (a[i] a[maxi]) {//i每走一步最大最小值就更新一下。 maxi i; } if (a[i] a[mini]) { mini i; } } //找到以后将最小值与a[begin]交换最大值与a[end]交换。 //因为每一轮遍历在区间[begin,end]里最终状态是a[begin]最小a[end]最大。 Swap(a[begin], a[mini]); Swap(a[end], a[maxi]); begin; end--; } }3.产生的异常。该序列很是特殊首元素就是全序列最大值即算法执行过程中下标为maxi,第二个元素是全序列最小值下标为mini但请别忘了首元素的下标也是begin在找到最小元素以后会执行交换操作即首元素与mini所对应元素进行交换那么1被换到了首元素这个时候maxi仍旧指向首元素但最大值9已经被换到了后面可谓货不对板。以下为第一轮遍历从开始到swap(begin,mini)的图示所以我们在最大元素被换走时应该更新一下maxi。以下为最终版代码(不要参考上面初版的代码)void SelectSort(int* a, int n) { int begin 0; int end n-1; while (begin end)//begin到end间无序需要找最大最小值 {//最终大的在右小的在左。 //找最大最小值的下标 int mini begin; int maxi begin; for (int i begin 1; i end; i) { if (a[i] a[maxi]) {//i每走一步最大最小值就更新一下。 maxi i; } if (a[i] a[mini]) { mini i; } } //找到以后将最小值与a[begin]交换最大值与a[end]交换。 //因为每一轮遍历在区间[begin,end]里最终状态是a[begin]最小a[end]最大。 Swap(a[begin], a[mini]); if (begin maxi) {//更新一下,防止begin与maxi重叠导致货不对板。 maxi mini; } Swap(a[end], a[maxi]); begin; end--; } }四.快速排序。1.算法描述。注意下面讲的“三分天下”其实是key将序列二分为左右两个区间。单趟动画left找比key大right找比key小让right先行找到目标停住left再行left找到后left停住right的值与left的值互换。在left与right相遇以后交换该位置与key的元素。整体在单趟完成以后整个序列可谓三分天下分为左区间目标数(a[key])右区间。然后借用二叉树里学到的递归思想再将左右区间分别拆开作为一个新序列再不断对新序列执行单趟操作执行完又三分天下又拆...直到拆到序列只剩一个元素为止。也就是每个单趟key都在二分序列如果每次单趟的分割都为二分那么整个递归就可以看成是一棵满二叉树。2.算法实现。单趟将left和right作为整体递归操作上的序列的左边界和右边界而在单趟排序里真正行使其效用的是begin和end。Ⅰ.代码展示暗藏错误void QuickSort(int* a, int left,int right) {//将left和right作为整体递归操作上的左边界和右边界而在单趟排序里真正行使其效用的是begin和end。 int begin left; int end right; int key a[begin]; //单趟。 while (begin end) {//左边找大右边找小 while(a[end] a[key]) { end--; } while(a[begin] a[key]) {//左边遇到比key小的就一直遍历遇到比key大就停止。 begin; } } //begin和end相遇以后交换key与当前位置数据。 Swap(key, a[begin]); }在代码实现过程中end或begin找到目标了就跳出其各自的while循环以达到停车的目的。Ⅱ. left做keyend先走begin与end的相遇点总是小于key的分析Ⅲ.小问题①.在这组数据遍历的过程中begin与end相遇后begin还在找比它大的结果就一脚油门开过了。所以要给寻找过程的while增加一个beginend的强制停车条件无论找没找到比begin大的遇到这个条件就停下来②.在单趟遍历最后一步a[begin]即a[5]与a[0](key)发生交换交换后a[5]确实为6了a[0]理应为3但为什么还是原来的值6呢key为一个局部变量那么它并不会代表序列中的a[0]它只是一个值当a[begin]的元素(3)与key(6)交换时a[begin]的3换给了key而非a[0],就导致a[0]仍旧为6。就像把钱拿给财务看似财务老板是一伙的结果财务跑路了老板压根没拿到钱。解决方案将key变成下标。③.在单趟最终排序以后目标值经过交换挪到了begin所对应的元素处此时key也要跟着挪窝毕竟下标key始终对应着目标值。单趟最终代码void QuickSort(int* a, int left,int right) {//将left和right作为整体递归操作上的左区间和右区间而在单趟排序里真正行使其效用的是begin和end。 int begin left; int end right; int key begin;//用key存储目标元素的下标 //单趟。 while (begin end) {//左边找大右边找小 while (begin end a[end] a[key]) { end--; } while (begin end a[begin] a[key])//循环里加一个begin end,防止相遇后不停车。 {//左边遇到比key小的就一直遍历遇到比key大就停止。 begin; } //begin和end都找到目标后二者交换。 Swap(a[begin], a[end]); key begin;//交换以后目标值移到了begin,此时key也得挪窝。 } //begin和end相遇以后交换key与当前位置数据。 Swap(a[key], a[begin]); }Ⅳ.前后指针法。int PartSort2(int* a, int left, int right) { //三数取中。 int midi GetMidi(a, left, right); Swap(a[left], a[midi]);//把大小中等的数换到最左不打乱之前的执行步骤。 int prev left; int cur left 1; int key left; while (cur right) { if (a[cur] a[key] prev ! cur)//防止自己和自己交换,同时执行prev的操作。 { Swap(a[cur], a[prev]); cur; } else { cur; } } Swap(a[prev], a[key]); key prev; return key; }整体(图请参考上面算法描述的整体部分)序列未排序前先有left和right两个最左最右的区间边界待进行一次单趟后区间三分天下。“三分天下”的区间[left,key - 1] key [key 1,right]。随后每个单独的区间作为一个新序列再次三分天下就这么一直递归往下分分到递归停止递归停止的条件此时left 0,right 1,a[key] 2,所以交换后key 1。带着这些值我们来分析交换后的区间区间为[00] 1 [2 1]这时就会发现问题这个小序列压根没有右区间而且正常区间怎么可能左边大于右边。所以我们可以看出结束的条件是:①.区间[0,0]左右边界相同,即只有一个元素。②.出现不存在的区间[2,1]即没有右区间。在下一次的单趟中两个老区间又各自变成了新的序列并进行单趟每个新序列中区间左边界变成了left右边界变成了right,所以 结束条件可写成left right.(其中leftright 对应①left right对应②最终代码void QuickSort(int* a, int left,int right) {//将left和right代表一个序列的左右区间的边界而在单趟排序里真正行使其效用的是begin和end。 //递归停止的条件要么区间只有一个元素left right),要么没有单边区间 if (left right) { return; } int begin left; int end right; int key left;//用key存储目标元素的下标 //单趟。 while (begin end) {//左边找大右边找小 while (begin end a[end] a[key]) { end--; } while (begin end a[begin] a[key])//循环里加一个begin end,防止相遇后不停车。 {//左边遇到比key小的就一直遍历遇到比key大就停止。 begin; } //begin和end都找到目标后二者交换。 Swap(a[begin], a[end]); } //begin和end相遇以后交换key与当前位置数据。 Swap(a[key], a[begin]); key begin;//交换以后目标值移到了begin,此时key也得挪窝。 //整体开始递归分治分为三个区间[left,key - 1],key,[key 1,right]。 QuickSort(a,left,key - 1); QuickSort(a,key 1,right); }3.复杂度的分析。因为这种排序的递归类似于满二叉树的递归所以递归层数(高度)可以看作logN,而每一次单趟中begin,end--,它们向中靠拢最终走的步数之和就是N,所以O(N) NlogN。4.当下代码的不足。递归次数或深度过多过大导致栈溢出。在遇到已经顺序的序列时再使用快速排序会出现栈溢出的情况。分析在算法中end先行去寻找比key小的数递归中每个单趟的开销也就是说把二分玩没了二叉树的框架也没了所以总开销直接降级成了O(N^2),立马变的跟冒泡一样成路边一条了同时深度变成了N,如果序列数据过多会使得深度过深导致栈溢出。优化方案Ⅰ.随机选key但不靠谱。Ⅱ.三数取中即取序列最左边最右边以及最中间三个数在三个数中找一个既不是最大也不是最小的数作为key。代码实现(注意下面的midi,left,right统统指下标而取中看的是数值大小)int GetMidi(int* a, int left, int right)//取中数作key,防止顺序栈溢出。 { int midi (left right) / 2; if (a[left] a[midi]) {//那个下标所对应的元素大小在中间就返回哪个下标。 if (a[midi] a[right]) { return midi; } else if (a[right] a[left]) { return left; } else return right; } else//a[left] a[midi] { if (a[midi] a[right]) { return midi; } else if (a[right] a[left]) { return left; } else return right; } }使用的时候注意使用完以后要将大小中等的数换到最左当key毕竟之前的算法都是建立在最左边的数作为key每次单趟二分的基础之上。Ⅲ.小区间优化在三数取中完了以后能够保证每个单趟都可以二分。快排如果每次单趟的分割都为二分那么整个递归就可以看成是一棵满二叉树。在学满二叉树的时候我们知道越接近叶子该层节点树占总节点数的比例就越大开销也就越大。所以我们可以把后几层的递归给去掉这样总开销就去掉了百分之八十如何做呢我们可以打组合技在遇到区间小的序列时用插入排序区间大再递归调用。代码if ((right - left 1) 10)//小区间优化不再递归分割排序减少递归次数。 { InsertSort(a left,right - left 1);//a是整个大序列的地址找目标小序列的地址要用a加上小序列的left。 }5.非递归实现快排。用递归实现快排如果深度过大会造成栈溢出的现象有没有既能用到递归思想又不会栈溢出的操作有的兄弟有的。我们直接利用栈来模拟实现递归毕竟栈这个数据结构开辟空间的时候用的是malloc,而这么开辟出来的空间存在堆区堆区有好几个G的空间存储空间比存储递归的栈区只有几兆要大得多。栈存在的目的就是为了存储每次递归时的区间。#includestack.h void QuickSortNonR(int* a, int left, int right)//非递归实现快排。 { ST st; STKInit(st); STKPush(st,right);//入栈顺序先右后左。可保证出栈先左后右更能符合递归先左后右 STKPush(st,left); while (!STKEmpty(st)) {//单趟。 int begin STKTopData(st); STKPop(st); int end STKTopData(st); STKPop(st); int key PartSort2(a, begin, end);//执行单趟操作并取key。 //区间[begin , key - 1] key [key 1 , end] //依旧入栈先右后左。 //模拟递归整体。 if (key 1 end) { STKPush(st, end); STKPush(st, key 1); } if (begin key - 1) { STKPush(st, key - 1); STKPush(st, begin); } } }五.归并排序。1.底层逻辑。合并两个有序序列a分成两个有序的区间begin1和begin2比较将小的那个对应的元素(a[begin])赋值给i随后赋值给i的begin往后就这么一直重复直到有个序列的begin到end为止。那如果另一个序列还没有到end怎么办此时就将这个序列的a[begin]赋值给i, 然后直到触底为止。但一个序列是乱序的该怎么保证它左右区间有序呢2.两个流程。可以利用递归的手法将序列不断拆解当拆解到左右区间均只剩一个元素时就能满足当下小序列左右区间都有序。拆解完以后开始从底层向上执行合并的操作依旧利用递归。当回到序列a时a一定有序。3.代码的实现。递归过程先左拆解后右拆解最后进行合并。类似于后续遍历的顺序。void _MergeSort(int* a,int* tmp,int begin,int end) { if (begin end) { return; } //分解。 int midi (begin end) / 2; _MergeSort(a, tmp, begin, midi); _MergeSort(a, tmp, midi 1, end);//如此划分避免偶数与偶数1构成的区间造成的死循环。 //归并。 int begin1 begin; int end1 midi; int begin2 midi 1; int end2 end; int i begin; while (begin1 end1 begin2 end2) { if (a[begin2] a[begin1]) { tmp[i] a[begin1];//先tmp[i] a[begin1]再i,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, sizeof(int) * (end - begin 1));//注意每一趟的begin不一定等于0 } void MergeSort(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(fail!); exit(-1); } _MergeSort(a,tmp,0,n - 1);//用子函数来执行递归和归并操作。 free(tmp); }注意①.拆分的时候区间一定要写成[begin,midi] [midi 1,end]!!②.memcpy里前两个参数。每次执行归并操作时 当下序列的初始为begin并不一定为0因此memcpy里前两个参数一定要加上begin。4.非递归实现。六.Count排序。1.算法描述。①.利用count数组统计原数组里数据出现的次数。原数组里元素的值是几就在count数组对应下标的元素上(count里的下标就代表原数组里元素的值)出现几次就几次。②.排序。统计完以后依照下标的自然次序以及出现次数将count里的下标写回原数组里。但此时会出现一个问题假设原数组里的最大的数比较大但数据总数又比较小那么按照这个数所开辟的空间count就会有很大的浪费,为了节省我们可以进行一个相对映射即count[a[i]-min] 。2.代码的实现。void CountSort(int* a, int n) { int min a[0]; int 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));//开辟空间count,并对其初始化。 if (count NULL) { perror(fail!); exit(-1); } //统计次数 for (int i 0; i n; i) { count[a[i] - min];//相对映射。 }//count[n]就代表n出现的次数。 //排序。 int j 0; for (int i 0; i range; i) { while (count[i]--) { a[j] i min; } } free(count); count NULL; }注意七.复杂度和稳定性的对比。1.稳定性。稳定性指值相同的元素排序前后相对位置不变。①.直接插入排序假设tmp一开始在比较的数后面直接插入排序可以规定tmp与比较的数相同时插到这个数后一个位置这样相对位置就不变。所以这种算法稳定。②.希尔排序相同数据预排序可能被分到不同组那么相对位置就变了就不稳定。③.选择排序(巨坑)。规定比a[mini]小的数才进行更新交换如果遇到两个相同的比a[mini]小的数按遍历的优先级也是前一个被换到begin的位置因此相对位置没变稳定了吗请看下图1的相对顺序没变但6的相对顺序变了。What can I say? 所以不稳定。④.堆排序一个堆里全部是相同的数一顿排序下来乱成一锅粥...所以一定不稳定。⑤.冒泡排序两个值相等可以不交换所以稳定。⑥.快排利用前后指针法 把这些代入这两句可以看出不稳定。⑦.归并排序在遭遇上面全是相同值的序列时begin1的值在前begin2的值在后归并时tmp[i]先等于a[begin1]最后到a[begin2]到tmp里时依旧begin1在前begin2在后所以稳定。所以综上,涉及Swap(交换位置)或者太复杂的算法一般都不太稳定。2.复杂度快排和归并走的单趟时间开销为N,两种算法利用的递归思想的开销类似于向上调整建堆的深度因此综合上说是logN,所以总开销是N*logN。堆排序先建堆后排序建堆利用向上调整时间开销为logN排序利用向下调整,时间开销为N直接插入排序最坏为倒序时间开销为12...n,即N^2