递归排序法—-分治排序

• ， 22 1月 2021
• 作者 847954981@qq.com
• 我的编程之路, 算法学习

递归排序法—-分治排序

原理：

利用二分法将一组数组分成n多段只有一个元素的数组，再将数组两两组合排序

前提：

设立两个函数，一个函数用于分化数组，一个函数用于合并数组的递归

import java.io.*;
 import java.util.Arrays;
 class test  
 {
     public static int[] paixu(int[] array){
         //用于递归的结束即分化为只有一个元素的数组
         if(array.length==1){
             return array;
         }
         int middle=array.length/2;
         //利用分化函数来完成数组的左右分化
         int[] le=paixu(sor(0,middle,array));
         int[] ri=paixu(sor(middle,array.length,array));
         int i=0,j=0;
         int index=0;//这里设立了坐标变量来整合数组
         while(i<le.length&&j<ri.length){
                 array[index]=ri[j];
                 j++;
             }else{
                 array[index]=le[i];
                 i++;
             }
             index++;
         }//此时循环结束，如果没用整合完成则代表左右两个数组有一个数组已经遍历到头（while判定里有一个已经不成立的），
        //在此基础下进行分类讨论分类讨论（ps：我感觉这里是易忽视点）
         if(i<le.length){
             for(int n=i;n<le.length;n++){
                 array[index]=le[n];
                 index++;
             }
         }
         if(j<ri.length){
             for(int m=j;m<ri.length;m++){
                 array[index]=ri[m];
                 index++;
             }
         }
         return array;
     }
     //用于分化数组的函数
     public static int[] sor(int left,int right,int[] array){
         int[] result=new int[right-left];
         for(int i=0;left<right;left++,i++){
             result[i]=array[left];
         }
         return result;
     }
     public static void main (String[] args) throws java.lang.Exception
     {
         int[] m={1,9,78,5,2,3,44,65,26,78,3,6,1,2};
         int[] p=paixu(m);
         System.out.println(Arrays.toString(p));
     }
 }