整站外包优化公司,设计网站的公司,建设网站一定要备案吗,凡科商城官网旗舰店⭐ 作者#xff1a;小胡_不糊涂 #x1f331; 作者主页#xff1a;小胡_不糊涂的个人主页 #x1f4c0; 收录专栏#xff1a;浅谈数据结构 #x1f496; 持续更文#xff0c;关注博主少走弯路#xff0c;谢谢大家支持 #x1f496; 总结 1. 归并排序2. 计数排序3. 排序… ⭐ 作者小胡_不糊涂 作者主页小胡_不糊涂的个人主页 收录专栏浅谈数据结构 持续更文关注博主少走弯路谢谢大家支持 总结 1. 归并排序2. 计数排序3. 排序算法复杂度及稳定性分析 在总结之前我们先介绍一下归并排序和计数排序
1. 归并排序 归并排序MERGE-SORT 是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide andConquer的一个非常典型的应用。 将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 代码实现
/*** 归并排序* 时间复杂度O(N*logN)* 空间复杂度O(logN)* 稳定性稳定的排序* 目前为止3个稳定的排序直接插入排序、冒泡排序、归并排序* param array*/public static void mergeSort(int[] array){mergeSortFun(array,0,array.length-1);}private static void mergeSortFun(int[] array,int start,int end){if(startend){return;}//拆分int mid(startend)/2;mergeSortFun(array,start,mid);mergeSortFun(array,mid1,end);merge(array,start,mid,end);//合并}private static void merge(int[] array,int left,int mid,int right){//定义拆分后的左边部分int s1left;int e1mid;//定义拆分后的右边部分int s2mid1;int e2right;//定义一个新数组存放合并后的数据int[] tmpnew int[right-left1];int i0;//tmp的下标//同时满足-证明两个归并段都有数据while(s1e1 s2e2){if(array[s1]array[s2]){tmp[i]array[s1];}else{tmp[i]array[s2];}}while(s1e1){tmp[i]array[s1];}while (s2 e2) {tmp[i]array[s2];}//把排好序的数据 拷贝回原来的数组array当中for(int j0;jtmp.length;j){array[jleft]tmp[j];}}归并排序可以解决海量数据的排序问题 外部排序排序过程需要在磁盘等外部存储进行的排序 前提 内存只有 1G需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序。 先把文件切分成 200 份每个 512 M分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以进行 2 路归并同时对 200 份有序文件做归并过程最终结果就有序了 2. 计数排序 基本思想 计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 代码实现
/*** 计数排序的场景* 指定范围内的数据* 时间复杂度 O(MAX(N,范围))* 空间复杂度O(范围)* 稳定性稳定的排序* param array*/public static void countSort(int[] array) {//寻找最大值、最小值int maxvaluearray[0];int minvaluearray[0];for(int i0;iarray.length;i){if(array[i]maxvalue){maxvaluearray[i];}if(array[i]minvalue){minvaluearray[i];}}int[] countarrnew int[maxvalue-minvalue1];//记录array中元素出现个数初始值都为0for(int i0;iarray.length;i){countarr[array[i]-minvalue];}int index0;//重新定义array下标for(int i0;icountarr.length;i){while(countarr[i]0){array[index]iminvalue;index;countarr[i]--;}}}3. 排序算法复杂度及稳定性分析 排序方法最好平均最坏空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定希尔排序O(n)O(n^1.3)O(n^2)O(1)不稳定堆排序O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定快速排序O(n * log(n))O(n * log(n))O(n^2)O(log(n)) ~ O(n)不稳定归并排序O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定
