前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏这篇博客会解析4个基础的排序算法基础排序的算法原理比较简单代码也比较好写基础排序的时间复杂度比较高因此在实际开发中很少会用到学习基础排序能提高我们的代码能力和排序思维先学透基础排序后面学习进阶排序的时候就更好理解而且基础排序相关的知识在面试时也可能会问到所以还是需要了解下的这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1排序知识排序就是给一个乱序的数组将其变成有序的有一个概念叫做排序的稳定性如果序列中存在两个值相同的元素排序前和排序后这两个元素的相对位置不变就认为是稳定排序否则就是不稳定排序就比如下面这个序列排序后2A必须要在2B之前排序分为两种内部排序和外部排序内部排序元素全部在内存中的排序外部排序元素太多不能同时放在内存中根据排序的要求不断在内外存之间移动数据序列内存是储存在内存条中的断电会丢失现在的新买的笔记本计算机基本上都是16G大一点的能上32G外存是储存在计算机上的硬盘的说存储空间是1T512G的基本上都是指外存外存中的内容断电不会丢失计算机中的各个盘就属于是外存存储在里面的文件不会因为关机就丢失了内存的数据访问速度块是外存的几十/几百倍但是存储空间小我们学习时写代码进行的排序都是内部排序因为数据规模比较小就算排序100W个int类型的数据这些数据的大小也不过4MB在实际开发中如果要排序很多数据比如上百G那就要在硬盘和内存中来回倒腾这些数据这里铁汁们了解下内部排序和外部排序是什么意思即可有关内存和外存的知识在JavaEE专栏中还会有详细的解析2插入排序插入排序的原理非常简单就是给定一个数组把这个数组分为两个部分有序区间已排序区间无序区间待排序区间初始情况下这个数组是没有排序的这时候有序区间为空无序区间就是整个数组每次选择无序区间的一个元素把这个元素插入到有序区间的合适位置上如下图初始时有序区间为空第一次插入就把9插入到无序区间中接下来每次都从后面选取一个元素插入到前面有序区间合适的位置中直到有有序区间的范围是整个数组写下插入排序(升序排序)的代码假设初始时无序区间的范围是[bound,arr.length - 1)先取出要进行插入的元素arr[bound]从后往前遍历(0,bound]这个区间设定下标为cur如果arr[cur]大于arr[bound]arr[cur]向后移动一步也就是arr[cur 1] arr[cur]如果arr[cur] arr[bound]就直接break跳出循环插入时就是让arr[cur 1] arr[bound]因为出遍历循环要不就是有序区间中的元素都大于arr[bound]cur走到-1的位置要不就是arr[cur]小于等于arr[bound]这两种情况都是把元素插入到cur后面的位置为了方便遍历有序区间可以上来把bound设置为1也就是有序区间中刚开始就有一个元素这样访问bound - 1就不会出现数组越界异常importjava.util.Arrays;publicclassTest{publicstaticvoidinsertSort(int[]arr){intbound1;intcur0;for(bound1;boundarr.length;bound){intvaluearr[bound];for(curbound-1;cur0;cur--){if(arr[cur]value){arr[cur1]arr[cur];}else{break;}}arr[cur1]value;}}publicstaticvoidmain(String[]args){int[]arr{9,5,2,7,1,4,8};insertSort(arr);System.out.println(Arrays.toString(arr));}}分析下时间复杂度对于每次插入来说要选取合适的插入位置时间复杂度是O(N)还会触发顺序表数组的元素搬运时间复杂度也是O(N)插入过程的时间复杂度还是O(N)要插入N次整体的时间复杂度就是O(N^2)插入排序的其空间复杂度是O(1)因为并没有创建额外的数组空间之类的只是创建了curbound这几个变量在循环时使用另外插入排序属于是稳定排序但这个也取决于我们代码怎么写如下这个if逻辑中我们写的是arr[cur] value如果出现arr[cur]等于value的情况是直接跳出循环的value是插到arr[cur]后面的是符合稳定性的如果if中的条件写的是arr[cur] value那arr[cur]等于value时arr[cur]就会后移cur继续向左移动这样value是插到arr[cur]前面的就不符合稳定性if(arr[cur]value){arr[cur1]arr[cur];}这个画个图试一下应该很好理解3希尔排序希尔排序又称为“谢尔排序”排序时把整个数组分为若干组针对每一组分别进行插入排序引入了gap概念表示同组相邻元素之间的间隔也表示分成了几组例如gap的值为3如下图颜色相同的就是一组分成了三组每组相邻元素之间的间隔就是3gap的值为2分组如下所示gap为1就是数组中所有元素是一个分组跟插入排序是一样的那希尔排序进行分组插入排序具体是如何操作的呢希尔排序是需要经过多次插入排序的例如gap的值设置为3、2、1数组先按照gap为3分成3组在每组中进行插排插入排序这样能确保每组的元素都是有序的再按照gap为2分为2组在每组中进行插排确保每组的元素是有序的最后gap为1也就是进行正常的插排也就是普通的插入排序这样最后数组整体一定是有序的最后的环节就相当于大火收汁希尔排序就相当于是在普通插入排序的基础上稍微优化了一些插入排序在两种情况下排序效率比较高数组的元素比较少数组中的元素已经基本有序了在希尔排序中刚开始gap的值比较大把整个数组分成了gap个小组每个小组中的元素就相对较少就符合第一种元素较少的情况排序效率就比较高后面gap的值越来越小但经过之前的排序数组中的元素已经相对比较有序了排序的效率也比较高在写代码时这个gap的值一般第一次取arr.length / 2后面每次gap gap / 2直到gap的值为1就排序完成了写个insertSortGap方法里面传入数组和gap在shellSort方法中调用insertSortGap方法即可insertSortGap在前面插入排序代码的基础上改一下即可对gap个分组进行轮流的排序每次cur移动gap距离publicstaticvoidinsertSortGap(int[]arr,intgap){for(inti0;igap;i){intbound1;intcur0;for(boundigap;boundarr.length;boundgap){intvaluearr[bound];for(curbound-gap;curi;cur-gap){if(arr[cur]value){arr[curgap]arr[cur];}else{break;}}arr[curgap]value;}}}publicstaticvoidshellSort(int[]arr){intgaparr.length/2;while(gap1){insertSortGap(arr,gap);gapgap/2;}}insertSortGap方法也有进阶的写法只需要两层for循环就够了外层循环让bound等于gap每次bound就可以认为是先处理第0组第一个元素的插入再处理1组第一个元素的插入…第一个元素的插入处理完后接着再处理第0组第二个元素的插入第1组第二个元素的插入以此类推内层循环cur之前写的结束条件是cur i现在没有i了直接写cur 0即可铁汁们可以画图细品下每次cur - gap因为i是小于gap的所以当cur等于i的时候下次再减去gapcur的值一定是小于0的publicstaticvoidinsertSortGap(int[]arr,intgap){intbound1;for(boundgap;boundarr.length;bound){intcur0;intvaluearr[bound];for(curbound-gap;cur0;cur-gap){if(arr[cur]value){arr[curgap]arr[cur];}else{break;}}arr[curgap]value;}}publicstaticvoidshellSort(int[]arr){intgaparr.length/2;while(gap1){insertSortGap(arr,gap);gapgap/2;}}希尔排序就是个数学游戏在日常开发中是用不到的虽然对插入进行了优化但是最坏时间复杂度仍然是O(N ^ 2)是比不过后面要介绍的一些高效率算法的至于希尔排序的平均时间复杂度是多少不同教材上有不同的答案例如n的1.25次方n的二分之三次方这个计算起来是非常复杂的而且取决于gap是如何设定的这里铁汁们了解下即可希尔排序因为没创建什么额外的数组空间空间复杂度为O(1)希尔排序属于不稳定排序当数组中出现两个相同的元素经过分组这两个元素很可能分到不同的组中在每个组中进行排序时靠后的元素就有可能跑到靠前的元素之前4直接选择排序直接选择排序的原理特别简单就是把数组划分为两个区间有序区间和无序区间初始时无序区间是空的如果是数组升序排序那就是每次都从无序区间中找出最小值加入到有序区间的末尾这样有序区间的范围就会越来越大直到有序区间的范围是整个数组那如何找出最小值找出后应该如何进行交换呢可以通过打擂台赛的方式从前到后遍历无序区间每个元素都跟无序区间的第一个元素比大小如果比第一个元素的值小就跟第一个元素交换位置这样一轮下来无序区间的最小值就到了前面接着把无序区间的第一个元素划分到有序区间中接着继续对无序区间继进行遍历重复上述过程写代码时用bound表示边界[0,bound)表示已排序的区间[bound,arr.length)表示未排序的区间当已排序区间为[bound,arr.length - 1)时数组就已经排好了因为这时候无序区间中只有一个元素这个元素一定是最小的在代码末尾加上个打印日志看下打印的效果publicstaticvoidselectSort(int[]arr){for(intbound0;boundarr.length-1;bound){for(intibound1;iarr.length;i){if(arr[i]arr[bound]){inttemparr[i];arr[i]arr[bound];arr[bound]temp;}}System.out.println(boundArrays.toString(arr));}}直接选择排序也属于是不稳定排序如下图这个例子中经历两轮排序后2’就到了2的前面直接选择排序的时间复杂度为O(N ^ 2)空间复杂度为O(1)5冒泡排序这个属于老生常谈的内容了在学习C语言时最先接触的排序应该就是冒泡排序例如要升序排序数组从前到后遍历数组当然也可以从后往前每两个元素之间比较下大小判断是否需要交换确保把大的元素放在后面这样一趟下来就能把最大值放到最后还可以加个优化如果内存循环一轮比较都没有需要交换位置的元素那就说明这个数组已经有序了直接跳出外层循环publicstaticvoidbubbleSort(int[]arr){for(inti1;iarr.length-1;i){booleanisSortedtrue;for(intj0;jarr.length-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;isSortedfalse;}}if(isSorted){break;}}}冒泡排序的时间复杂度是O(N^2)空间复杂度为O(1)因为判断条件是只有前面元素大于后面元素时才进行交换所以冒泡排序是稳定的排序结语这四种基础排序的规律总结如下插入排序顺序表插入.时间复杂度 O (N^2)空间复杂度 O (1)稳定性稳定希尔排序分组进行插入排序时间复杂度 最坏 O (N^2), 平均不知道取决于 gap 序列.空间复杂度 O (1)稳定性不稳定。分组之下分别插排就会使相同值的相对顺序改变。相同值可能在不同的分组中直接选择排序从待排序区间中通过打擂台的方式找到最小值放到待排序区间的开头位置.时间复杂度 O (N^2)空间复杂度 O (1)稳定性不稳定。交换之下可能出现相同值的顺序改变.冒泡排序比较交换相邻元素每一趟找出最小值 / 最大值时间复杂度: O (N^2)空间复杂度: O (1)稳定性稳定.以上就是今天的所有内容啦完结撒花