排序的分类直接插入排序直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。voidInsertSort(int*arr,intn){for(inti0;in-1;i){intendi;//先保存要排的数inttmparr[end1];while(end0){if(arr[end]tmp){//这里不能使用swap交换因为这样开销大效率低arr[end1]arr[end];end--;}//需要elseelse{break;}}arr[end1]tmp;}}直接插入排序的特性总结元素集合越接近有序直接插⼊排序算法的时间效率越高O(n)反之当排升序时大的数据在前小的数据在后时效率最低时间复杂度O(n^2)最坏情况下希尔排序希尔排序法的基本思想是先选定⼀个整数通常是gap n/31(1是为了保证gap最后为1)把待排序文件所有记录分成各组所有的距离相等的记录分在同⼀组内并对每一组内的记录进行排序然后gapgap/31得到下⼀个整数再将数组分成各组进行插入排序当gap1时就相当于直接插入排序。voidShellSort(int*arr,intn){intgapn;while(gap1){gapgap/31;//注in-gapi一次性遍历不用i igap减少了代码循环for(inti0;in-gap;i){intendi;inttmparr[endgap];while(end0){if(arr[end]tmp){arr[endgap]arr[end];end-gap;}else{break;}}arr[endgap]tmp;}}}当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。时间复杂度通过上面分析可以画出这样的曲线图因此希尔排序在最初和最后的排序的次数都为n即前⼀阶段排序次数是逐渐上升的状态当到达某一顶点时排序次数逐渐下降至n而该顶点的计算暂时无法给出具体的计算过程。直接选择排序voidSelectSort(int*arr,intn){intleft0,rightn-1;while(leftright){intminleft,maxleft;for(intileft;iright;i){if(arr[i]arr[min]){//这里可不能写成//swap(arr[left], arr[min]);mini;}if(arr[i]arr[max]){maxi;}}//下面代码很重要因为当leftright时没有这个代码将出错if(maxleft){maxmin;}swap(arr[left],arr[min]);swap(arr[right],arr[max]);left;right--;}}直接选择排序基本思想在元素集合 array[i]–array[n-1] 中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换。直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(n^2)堆排序//排升序//向下调整算法voidAdjustDown(int*arr,intparent,intn){intchildparent*21;while(childn){if(arr[child1]arr[child]child1n){child;}if(arr[child]arr[parent]){swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}}voidHeapSort(int*arr,intn){for(inti(n-1-1)/2;i0;i--){AdjustDown(arr,i,n);}for(intin-1;i0;i--){swap(arr[0],arr[i]);AdjustDown(arr,0,i);}}时间复杂度O(nlog^n)冒泡排序voidBubbleSort(int*arr,intn){for(inti0;in-1;i){intexchange1;for(intj0;jn-1-i;j){if(arr[j]arr[j1]){swap(arr[j],arr[j1]);exchange0;}}if(exchange){break;}}}时间复杂度O(n^2)快速排序基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。重点是如何将基准值放到对应的位置hoare版本算法思路1.确定基准值创建左右指针2.从右向左找出比基准值小的数据从左向右找出比基准值大的数据左右指针数据交换进入下次循环代码#includestdio.hvoidswap(int*x,int*y){inttmp*x;*x*y;*ytmp;}int_QuickSort(int*arr,intleft,intright){intkeyileft;left;while(leftright){//while (arr[right] arr[keyi] left right)//这里数值比较一定不能当数组数据全部为重复时会使时间复杂度从O(nlog^n)变成O(n^2)while(leftrightarr[right]arr[keyi]){right--;}while(leftrightarr[left]arr[keyi]){left;}if(leftright)//必须要有{swap(arr[left],arr[right--]);//要记得leftright--}}swap(arr[keyi],arr[right]);returnright;}voidQuickSort(int*arr,intleft,intright){if(leftright){return;}//找基准值 keyindexintkeyi_QuickSort(arr,left,right);QuickSort(arr,left,keyi-1);//注意这里是传keyi-1不是keyiQuickSort(arr,keyi1,right);}intmain(){intarr[7]{6,3,5,0,7,6,1};QuickSort(arr,0,6);for(inti0;i7;i){printf(%d ,arr[i]);}return0;}注意QuickSort递归的实参传keyi-1.这里循环为什么要如图第一次循环后left与right在9相遇如果此时跳出循环6会与9交换则不满足基准值左边都比基准值小。3.为什么必须要有如图没有时left与right在6相遇会陷入死循环.4.先判断边界再访问。不然会造成数组越界。挖坑法算法思想创建左右指针。⾸先从右向左找出比基准小的数据找到后立即放入左边坑中当前位置变为新的坑然后从左向右找出比基准大的数据找到后立即放入右边坑中当前位置变为新的坑结束循环后将最开始存储的分界值放入当前的坑中返回当前坑下标即分界值下标如以最左边为hole创建left与right进行遍历。在这里插入代码片voidswap(int*x,int*y){inttmp*x;*x*y;*ytmp;}int_QuickSort(int*arr,intleft,intright){intkeyarr[left];intholeleft;while(leftright){while(leftrightarr[right]key){right--;}arr[hole]arr[right];holeright;while(leftrightarr[left]key){left;}arr[hole]arr[left];holeleft;}arr[hole]key;returnhole;}voidQuickSort(int*arr,intleft,intright){if(leftright){return;}//找基准值 keyindexintkeyi_QuickSort(arr,left,right);QuickSort(arr,left,keyi-1);//注意这里是传keyi-1不是keyiQuickSort(arr,keyi1,right);}intmain(){intarr[7]{1,2,3,4,5,6,7};QuickSort(arr,0,6);for(inti0;i7;i){printf(%d ,arr[i]);}return0;}挖矿法用的比较少因为其本身就有“坑”当数据全部为重复数据时算法会陷入死循环。如果把内层循环加上不会死循环但快排的递归次数可能会变成n^2lomuto前后指针法int_QuickSort(int*arr,intleft,intright){intkeyileft;intpreleft;intcurpre1;while(curright){//冗长代码/* while (cur right arr[cur] arr[keyi]) { cur; } if (cur right pre ! cur) { swap(arr[cur], arr[pre]); } cur;*/while(arr[cur]arr[keyi]pre!cur){swap(arr[cur],arr[pre]);}cur;}swap(arr[keyi],arr[pre]);returnpre;}voidQuickSort(int*arr,intleft,intright){if(leftright){return;}//找基准值 keyindexintkeyi_QuickSort(arr,left,right);QuickSort(arr,left,keyi-1);//注意这里是传keyi-1不是keyiQuickSort(arr,keyi1,right);}时间复杂度:一般O(nlogn),在待排序数组有序时为最坏情况O(n2);空间复杂度:O(nlogn)~O(n2);归并排序归并排序是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法的⼀个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。图解代码实现#includestdio.h#includestdlib.hvoidmergeSort(int*arr,int*tmp,intl,intr){if(lr){return;}intmidl(r-l)/2;mergeSort(arr,tmp,l,mid);mergeSort(arr,tmp,mid1,r);//数组合并intbegin01l,end01mid,begin02mid1,end02r,indexl;while(begin01end01begin02end02){if(arr[begin01]arr[begin02])//这里不写就会使排序不稳定{tmp[index]arr[begin01];}else{tmp[index]arr[begin02];}}while(begin01end01){tmp[index]arr[begin01];}while(begin02end02){tmp[index]arr[begin02];}//tmp导入原数组中for(intil;ir;i)//i需要rr是数组下标{arr[i]tmp[i];}}intmain(){intarr[7]{3,4,4,5,2,2,1};int*tmp(int*)malloc(7*sizeof(arr[0]));mergeSort(arr,tmp,0,6);//传6free(tmp);for(inti0;i7;i){printf(%d ,arr[i]);}return0;}时间复杂度O(nlog^n)空间复杂度O(n),虽然递归空间logn但主体所占空间还是n用非递归思想实现归并排序#includestdio.h#includestdlib.h#includestring.hvoidmergeSort(int*arr,intn){int*tmp(int*)malloc(n*sizeof(arr[0]));intgap1;while(gapn)//当gapn时已经有序不需要进入循环{//根据gap划分组两两合并for(inti0;in;i2*gap){intbegin1i,end1igap-1,begin2igap,end2i2*gap-1,indexi;if(begin2n)//如当gap1n奇数时会出现这种情况。{break;}if(end2n){end2n-1;}//两个有序序列进行合并(在for里while(begin1end1begin2end2){if(arr[begin1]arr[begin2]){tmp[index]arr[begin1];}else{tmp[index]arr[begin2];}}while(begin1end1){tmp[index]arr[begin1];}while(begin2end2){tmp[index]arr[begin2];}//拷贝的大小不是2*gap是end2-i1因为当end2被修为n-1时//实际合并的元素不足2*gap个。memcpy(arri,tmpi,(end2-i1)*sizeof(arr[0]));}//memcpy不能等一轮合并完才改变arr因为当触发break时tmp里所对应的值是随机值//memcpy(arr, tmp, n * sizeof(int));gap*2;}free(tmp);}intmain(){intarr[9]{3,4,4,5,2,2,1,6,0};mergeSort(arr,9);for(inti0;i9;i){printf(%d ,arr[i]);}return0;}以上方法都属于比较排序(通过比较元素之间的大小关系来确定元素先后顺序的排序算法)下面我们来学习非比较排序计数排序计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤1统计相同元素出现次数2根据统计的结果将序列回收到原来的序列中举个例子先把需要排序数组里的各元素个数整理出来再创建一个数组创建数组里的数据是需要排序数组的元素出现次数。没有出现的数字我们将其写为0对于这里创建数组需要注意如果我们按数值开辟空间如下图数组难道我们开辟从0~109的数组吗这会造成浪费所以我们按范围开辟空间代码voidCountSort(int*arr,intn){//max,min用具体值表示比用数组下标表示对后面的maxmin的使用更方便//因为后面会对arr的值进行重新赋值intmaxarr[0],minarr[0];for(inti1;in;i){if(arr[i]max){maxarr[i];}if(arr[i]min){minarr[i];}}intrangemax-min1;int*tmp(int*)calloc(range,sizeof(arr[0]));for(inti0;in;i){tmp[arr[i]-min];}intindex0;for(inti0;irange;i){while(tmp[i]--){//arr[index] tmp[i] min;错误arr[index]imin;}}}时间复杂度O(nrange),range也是变量由max与min决定。空间复杂度O(range)稳定性稳定但是问题又来了假如数组为{12341000000}那我们还以max-min来开辟空间那依旧会浪费大量空间为此计数排序只适合数值分布均匀的数值排序排序算法复杂度与稳定性总结