【初阶数据结构】 升沉有序的平仄 排序

点击展开/收起 文章目录文章目录排序分类1. 插入排序直接插入排序希尔排序2. 选择排序选择排序堆排序3. 归并排序归并排序递归实现归并排序的非递归实现希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力在学习编程中,把无序的东西变的有序在生活中很常见,排序算法的复杂度对我们算法优劣还是有很大的影响进入排序讲解之前我要教大家写测试用例,来测试我们写的排序的快慢分为四步走:在堆上创建N个数据的空间种时间种子,用循环将生成的随机数,加入到开辟的空间中去利用time.h里面的begin(),end()函数,记录当前的时间,和程序结束的时间,然后相减,得到程序运行的时间释放开辟的空间,防止内存泄漏voidTestOP(){intN100000;srand((unsignedint)time(0));int*a1(int*)malloc(sizeof(int)*N);int*a2(int*)malloc(sizeof(int)*N);for(inti0;iN;i){a1[i]rand()i;//a1[i] rand();a2[i]a1[i];}intbegin1clock();InsertSort(a1,N);intend1clock();intbegin2clock();ShellSort(a2,N);intend2clock();printf(InsertSort:%d\n,end1-begin1);printf(ShellSort: %d\n,end2-begin2);free(a1);free(a2);}排序分类以下是我要讲的全部排序,当然这一次性肯定讲不完,我会看情况分为两次或者三次讲完1. 插入排序直接插入排序图是很清楚默认排的是升序,遇到小的就往前插入,直到遇到,比自己小的停止,这种效率还是很高的,时间复杂度虽然是O(N^2) , 但出现O(N^2), 情况还是比较难,要求是高度升序才有可能,所以作为O(N^2)的排序方式还是比较快的.以下是代码实现演示过程voidInsertSort(int*a,intn){for(intj0;jn-1;j){intendj;inttmpa[end1];while(end0){if(a[end]tmp){a[end1]a[end];end--;}else{break;}a[end1]tmp;}}}希尔排序希尔排序时间复杂度为O(N^1.3),不用掌握计算,因为需要很多数学的专业知识从上面看出其实选择排序这个结构还是很不错的一个结构,我们能不能改进一下结构,让他的排序速度变快呢?我们可以看出与插入排序对比,希尔排序多了一个gap组gap的选取,有大量验证,gap/3得到的排序速度最快,gap/31是为了保证gap不为零,gap既是组数又是一次跳的步数,gap是干什么用的呢?gap是用来把我们的数据分割成gap组分别进行直接插入排序如图所示第二个循环的过程,随i变化,分别开始,进行直接插入排序,那结束条件是什么?第二个循环的结束条件最外层调整gap使得gap等于1时最后一次排序voidShellSort(int*a,intn){intgapn;while(gap1){gapgap/31;for(inti0;in-gap;i){intendi;inttmpa[endgap];while(end0){//类比直接插入排序,把1换成gapif(a[end]tmp){//这里间隔是gap所有加减都gapa[endgap]a[end];end-gap;}elsebreak;a[endgap]tmp;}}}}对比一下1000000个数据下,直接插入排序和希尔排序的速度可以看出差距还是挺大的2. 选择排序选择排序这里逻辑很简单,就是每轮遍历,选出最大最小的,放在begin和last位置处**注意:**这里当begin与max相重合时,Swap(a[begin], a[min]);后a[max]被交换到a[min]的位置要更新max位置voidSelectSort(int*a,intn){intbegin,last,min,max;;begin0;lastn-1;while(beginlast){minmaxbegin;for(intibegin1;ilast;i){if(a[i]a[max]){maxi;}if(a[i]a[min]){mini;}}Swap(a[begin],a[min]);if(maxbegin)//坑点,如果相等要进行更新max{minmax;}Swap(a[last],a[max]);begin;last--;}}堆排序我这里演示的是建大堆排升序思路是每次把最大的数据堆顶数据与堆的最后一个数据交换位置,size- -;再重新找次大的数据,再重复此过程下面演示堆的建堆过程还有排序过程voidHeapDown(int*a,intsize,intparent){intchild2*parent1;while(childsize){if(child1sizea[child1]a[child]){child;}if(a[parent]a[child]){Swap(a[parent],a[child]);parentchild;child2*parent1;}else{break;}}}voidHeapSort(int*a,intsize){for(intisize;i1;i--){Swap(a[0],a[i-1]);HeapDown(a,i-1,0);}}堆排序与选择排序对比100000,由于选择排序太慢,这里就用十万个数据由此看出直接插入排序还是比选择排序快很多的3. 归并排序归并排序递归实现归并是一种分而治之的思想,先分成小组,单个的,再进行顺序归并再这里最坏分割时间复杂度是O(logN)注意这里在分割区间时的小细节问题void_Mergesort(int*a,int*tmp,intbegin,intend){if(beginend)return;else{intmid(beginend)/2;//beginend返回这里往下走,进行有序合并,就像顺序表篇讲的合并有序数组_Mergesort(a,tmp,begin,mid);_Mergesort(a,tmp,mid1,end);intbegin1begin;intend1mid;intbegin2mid1;intend2end;inti0;while(begin1end1begin2end2){//有序合并if(a[begin1]a[begin2]){tmp[i]a[begin1];}else{tmp[i]a[begin2];}}//有一组有剩余,拷贝到tmp中去while(begin1end1){tmp[i]a[begin1];}while(begin2end2){tmp[i]a[begin2];}//注意着里要从begin开始拷贝,拷贝回a中//拷贝回去是从a[begin]拷,对于最左边begin0,但对于其他的递归分割的begin却不是0memcpy(abegin,tmp,sizeof(int)*(end-begin1));}}voidMergesort(int*a,intn){int*tmp(int*)malloc(sizeof(int)*n);if(tmpNULL){perror(malloc fail);return;}_Mergesort(a,tmp,0,n-1);free(tmp);tmpNULL;}归并排序的非递归实现非递归实现的大坑:就是数据不是整数gap倍,时的归并;归并会出现访问越界的情况我们来仔细分析以下的越界情况:三种越界情况展示:在这里我们可以归纳一下越界逻辑你会发现,end1越界,和end1,begin2越界其实是一种情况,第二区间不存在都表示后面没有数了不用归并了// 边界修正 if (end1 n|| begin2 n) { end1 n - 1;不归并,直接把尾区间给end1;往下走 break; // 第二区间不存在跳过 } if (end2 n) end2 n - 1;第二区间还有数继续归并void_Mergesort2(int*a,int*tmp,intbegin,intend){intnend-begin1;// 总元素个数intgap1;while(gapn)// 改用 n更清晰{for(inti0;in;i2*gap){intbegin1i;intend1igap-1;intbegin2igap;intend2i2*gap-1;// 边界修正if(end1n)end1n-1;if(begin2n)break;// 第二区间不存在跳过if(end2n)end2n-1;intleftbegin1;// 保存原始左边界intji;// tmp 中的起始索引while(begin1end1begin2end2){if(a[begin1]a[begin2])tmp[j]a[begin1];elsetmp[j]a[begin2];}while(begin1end1)tmp[j]a[begin1];while(begin2end2)tmp[j]a[begin2];// 正确拷贝从 left 位置开始长度为 j - leftmemcpy(aleft,tmpleft,sizeof(int)*(j-left));}gap*2;}}//非递归实现归并voidMergesort2(int*a,intn){int*tmp(int*)malloc(sizeof(int)*n);if(tmpNULL){perror(malloc fail);return;}_Mergesort2(a,tmp,0,n-1);free(tmp);tmpNULL;}希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力