合并排序:合并排序其实也叫做归并排序,只是叫法不一样罢了,本质还是使用分治的思想实现对n个元素进行排序的算法,其基本思想是:将待排序的元素分解为大致相同的两个子数组,分别对两个子集合进行排序,最终将排好序的字数组进行合并,最终达到整个数组有序的过程。

程序代码如下:

//递归拆分排序
public static int[] gbSort(int[] arr,int low,int high){

        int mid = (low+high)/2;
        if(low<=high){

        gbSort(arr,low,mid);
        gbSort(arr,mid+1,high);
        merge(arr,low,mid,high);

}
       
        return arr;
}

//合并排序好的数组

public static void merge(int[] arr,int low,int mid,int high){

          int[] temp = new int[high-low+1];
          int i = low;
          int j = mid+1;
          int k = 0;
           
          while(i<=mid && j<=high){
        if(arr[i] < arr[j]){
        temp[k++] = arr[i++];
}else{

temp[k++] = arr[j++];
}
}
       while(i<=mid){
        
        temp[k++] = arr[i++];
}
 while(j<=high){
        
        temp[k++] = arr[j++];
}

for(int x = 0;x<temp.length;x++){
    arr[x+low] = arr[x];
}




}






合并排序算法分析:事实上对于给定的一个数组arr,通常存在着排好序的多个子程序段,例如,数组中存在arr={4,8,3,7,1,5,6,2},

其中的子数组段{4,8}和{3,7}和{1,5,6}和{2}已经是排好序的了,我们只需要对其进行一定程度的合并就可以达到最终的目的。

将上面的子数组段合并和可以得到{3,4,7,8}和{1,2,5,6}子数组段,继续合并排序好的子数组段,最终达到整个数组排好序。