数据算法排序之归并排序

我不是女神ヾ 2023-10-07 16:19 34阅读 0赞

> 在你渐渐迷失在你的人生道路上的时候，千万不要因为走的太久，而忘记了我们为什么出发，做码农，也要清楚自己如何才能用有效的土地种植出 出色的产品，于是细节就需要把握一下。

如果你有兴趣可以关注一下公众号 biglead 我的大前端生涯，获取每日学习资料

> 排序是一个非常经典的问题，它以一定的顺序对一个数组（或一个列表）中的项进行重新排序（可以进行比较，例如整数，浮点数，字符串等）（增加，非递减，递减， 增加，词典等）。  
> 有许多不同的排序算法，每个都有其自身的优点和局限性  
> 引用于 https://visualgo.net/zh

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

*  算法复杂度：O（nlogn）
 *  核心思想：分治

如我这里有一组数据，归并排序过程描述如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psMTg2MDM1NDM1NzI_size_16_color_FFFFFF_t_70]

我们把上面的流程图合到一起就是如下：

![在这里插入图片描述][20210510133829191.png_pic_center]

--------------------

![在这里插入图片描述][2021051014353249.gif_pic_center]

分割的过程中其实可理解为就是以二分法将数组分割成最小单元，如下图所示分析了一下最后一步的合并过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psMTg2MDM1NDM1NzI_size_16_color_FFFFFF_t_70 1]

//归并排序
      @Test
      public void mergeSortFunction2(){
        
        //待排序数组
        int arr[]={
        6,5,3,1,8,7,2,4};
        int len = arr.length;
        //临时数组
        int[] result = new int[len];
        //排序
        sort(arr,result);
    
        System.out.println(Arrays.toString(result));
      }

public static void sort(int []arr,int []temp ){
        
        sort(arr,0,arr.length-1,temp);
      }
      private static void sort(int[] arr,int left,int right,int []temp){
        
        if(left<right){
        
          int mid = (left+right)/2;
          //左边归并排序，使得左子序列有序
          sort(arr,left,mid,temp);
          //右边归并排序，使得右子序列有序
          sort(arr,mid+1,right,temp);
          //将两个有序子数组合并操作
          merge(arr,left,mid,right,temp);
        }
      }
      private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
        
          if(arr[i]<=arr[j]){
        
            temp[t++] = arr[i++];
          }else {
        
            temp[t++] = arr[j++];
          }
        }
        while(i<=mid){
        //将左边剩余元素填充进temp中
          temp[t++] = arr[i++];
        }
        while(j<=right){
        //将右序列剩余元素填充进temp中
          temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
        
          arr[left++] = temp[t++];
        }
      }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psMTg2MDM1NDM1NzI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210510140517809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psMTg2MDM1NDM1NzI=,size_16,color_FFFFFF,t_70
[20210510133829191.png_pic_center]: https://img-blog.csdnimg.cn/20210510133829191.png#pic_center
[2021051014353249.gif_pic_center]: https://img-blog.csdnimg.cn/2021051014353249.gif#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psMTg2MDM1NDM1NzI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210510141934452.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psMTg2MDM1NDM1NzI=,size_16,color_FFFFFF,t_70