企业官网建设流程全解析

前言❤️❤️

hello hello💕，这里是洋不写bug~😄，欢迎大家点赞👍👍，关注😍😍，收藏🌹🌹
这篇博客会解析4个基础的排序算法，基础排序的算法原理比较简单，代码也比较好写，基础排序的时间复杂度比较高，因此在实际开发中很少会用到
学习基础排序能提高我们的代码能力和排序思维，先学透基础排序，后面学习进阶排序的时候就更好理解，而且基础排序相关的知识在面试时也可能会问到，所以还是需要了解下的💪💪💪
这个专栏的数据结构是代码都是用Java来写的，JavaSE专栏现在已经全部更新完成，铁汁们复习基础知识时非常推荐使用，可以试一下💪💪💪

🎇个人主页：洋不写bug的博客
🎇所属专栏：数据结构专栏
🎇复习Java基础知识：Java学习之旅，从入门到进阶
🎇铁汁们对于数据结构基础的各种核心知识（不太常用的也有😆），都可以在上面的数据结构专栏学习，专栏正在持续更新中🐵🐵，有问题可以写在评论区或者私信我哦~

1，排序知识

• 排序就是给一个乱序的数组，将其变成有序的，有一个概念叫做排序的稳定性，如果序列中存在两个值相同的元素，排序前和排序后，这两个元素的相对位置不变，就认为是稳定排序，否则就是不稳定排序，就比如下面这个序列，排序后2A必须要在2B之前

• 排序分为两种：内部排序和外部排序

1. 内部排序：元素全部在内存中的排序
2. 外部排序，元素太多不能同时放在内存中，根据排序的要求，不断在内外存之间移动数据序列

• 内存是储存在内存条中的，断电会丢失，现在的新买的笔记本计算机基本上都是16G，大一点的能上32G
• 外存是储存在计算机上的硬盘的，说存储空间是1T，512G的，基本上都是指外存，外存中的内容断电不会丢失，计算机中的各个盘就属于是外存，存储在里面的文件不会因为关机就丢失了
• 内存的数据访问速度块，是外存的几十/几百倍，但是存储空间小

• 我们学习时写代码进行的排序都是内部排序，因为数据规模比较小，就算排序100W个int类型的数据，这些数据的大小也不过4MB
• 在实际开发中，如果要排序很多数据，比如上百G，那就要在硬盘和内存中来回倒腾这些数据，这里铁汁们了解下内部排序和外部排序是什么意思即可，有关内存和外存的知识在JavaEE专栏中还会有详细的解析

2，插入排序

插入排序的原理非常简单，就是给定一个数组，把这个数组分为两个部分：

1. 有序区间（已排序区间）
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){intbound=1;intcur=0;for(bound=1;bound<arr.length;bound++){intvalue=arr[bound];for(cur=bound-1;cur>=0;cur--){if(arr[cur]>value){arr[cur+1]=arr[cur];}else{break;}}arr[cur+1]=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)，因为并没有创建额外的数组空间之类的，只是创建了cur，bound这几个变量在循环时使用

• 另外，插入排序属于是稳定排序，但这个也取决于我们代码怎么写，如下，这个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[cur+1]=arr[cur];}

  • 这个画个图试一下，应该很好理解

  3，希尔排序

  • 希尔排序又称为“谢尔排序”，排序时把整个数组分为若干组，针对每一组分别进行插入排序，引入了gap概念，表示同组相邻元素之间的间隔，也表示分成了几组

  • 例如gap的值为3，如下图，颜色相同的就是一组，分成了三组，每组相邻元素之间的间隔就是3

  
  
  
  

  • gap的值为2，分组如下所示：
  • gap为1，就是数组中所有元素是一个分组，跟插入排序是一样的

  
  
  

  • 那希尔排序进行分组插入排序，具体是如何操作的呢？
  • 希尔排序是需要经过多次插入排序的，例如gap的值设置为3、2、1
  1. 数组先按照gap为3分成3组，在每组中进行插排（插入排序），这样能确保每组的元素都是有序的
  2. 再按照gap为2分为2组，在每组中进行插排，确保每组的元素是有序的
  3. 最后gap为1，也就是进行正常的插排，也就是普通的插入排序，这样最后数组整体一定是有序的，最后的环节就相当于大火收汁🐵

  
  
  

  • 希尔排序就相当于是在普通插入排序的基础上稍微优化了一些，插入排序在两种情况下排序效率比较高：
  1. 数组的元素比较少
  2. 数组中的元素已经基本有序了
  • 在希尔排序中，刚开始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(inti=0;i<gap;i++){intbound=1;intcur=0;for(bound=i+gap;bound<arr.length;bound+=gap){intvalue=arr[bound];for(cur=bound-gap;cur>=i;cur-=gap){if(arr[cur]>value){arr[cur+gap]=arr[cur];}else{break;}}arr[cur+gap]=value;}}}publicstaticvoidshellSort(int[]arr){intgap=arr.length/2;while(gap>=1){insertSortGap(arr,gap);gap=gap/2;}}

  
  
  

  • insertSortGap方法也有进阶的写法，只需要两层for循环就够了，外层循环让bound等于gap，每次bound++，就可以认为是先处理第0组第一个元素的插入，再处理1组第一个元素的插入…第一个元素的插入处理完后，接着再处理第0组第二个元素的插入，第1组第二个元素的插入，以此类推
  • 内层循环cur之前写的结束条件是cur >= i，现在没有i了，直接写cur >= 0即可，铁汁们可以画图细品下，每次cur -= gap，因为i是小于gap的，所以当cur等于i的时候，下次再减去gap，cur的值一定是小于0的

  publicstaticvoidinsertSortGap(int[]arr,intgap){intbound=1;for(bound=gap;bound<arr.length;bound++){intcur=0;intvalue=arr[bound];for(cur=bound-gap;cur>=0;cur-=gap){if(arr[cur]>value){arr[cur+gap]=arr[cur];}else{break;}}arr[cur+gap]=value;}}publicstaticvoidshellSort(int[]arr){intgap=arr.length/2;while(gap>=1){insertSortGap(arr,gap);gap=gap/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(intbound=0;bound<arr.length-1;bound++){for(inti=bound+1;i<arr.length;i++){if(arr[i]<arr[bound]){inttemp=arr[i];arr[i]=arr[bound];arr[bound]=temp;}}System.out.println(bound+"："+Arrays.toString(arr));}}

  
  
  

  • 直接选择排序也属于是不稳定排序，如下图，这个例子中，经历两轮排序后，2’就到了2的前面
  • 直接选择排序的时间复杂度为O(N ^ 2)，空间复杂度为O(1)

  5，冒泡排序

  • 这个属于老生常谈的内容了，在学习C语言时，最先接触的排序应该就是冒泡排序，

  • 例如要升序排序数组，从前到后遍历数组（当然也可以从后往前），每两个元素之间比较下大小，判断是否需要交换，确保把大的元素放在后面，这样一趟下来，就能把最大值放到最后

  • 还可以加个优化，如果内存循环一轮比较都没有需要交换位置的元素，那就说明这个数组已经有序了，直接跳出外层循环

  publicstaticvoidbubbleSort(int[]arr){for(inti=1;i<=arr.length-1;i++){booleanisSorted=true;for(intj=0;j<arr.length-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;isSorted=false;}}if(isSorted){break;}}}

  
  
  

  • 冒泡排序的时间复杂度是O(N^2)，空间复杂度为O(1)，因为判断条件是只有前面元素大于后面元素时，才进行交换，所以冒泡排序是稳定的排序

  结语

  • 这四种基础排序的规律总结如下：

  1. 插入排序：顺序表插入.
     时间复杂度 O (N^2)
     空间复杂度 O (1)
     稳定性：稳定

  2. 希尔排序：分组进行插入排序
     时间复杂度 最坏 O (N^2), 平均不知道，取决于 gap 序列.
     空间复杂度 O (1)
     稳定性：不稳定。分组之下，分别插排，就会使相同值的相对顺序改变。相同值可能在不同的分组中

  3. 直接选择排序：从待排序区间中，通过打擂台的方式找到最小值，放到待排序区间的开头位置.
     时间复杂度 O (N^2)
     空间复杂度 O (1)
     稳定性：不稳定。交换之下，可能出现相同值的顺序改变.

  4. 冒泡排序：比较交换相邻元素，每一趟找出最小值 / 最大值
     时间复杂度: O (N^2)
     空间复杂度: O (1)
     稳定性：稳定

  
  
  
  .以上就是今天的所有内容啦～完结撒花～🥳🎉🎉