排序算法一：归并排序

一：归并排序原理

归并排序利用的是分治的思想实现的，对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的子序列，之后对子序列排序，最后再用递归方法将排好序的子序列合并成为有序序列。合并两个子序列时，需要申请两个子序列加起来长度的内存，临时存储新的生成序列，再将新生成的序列赋值到原数组相应的位置。

二：归并排序复杂度

平均时间复杂度均为O(nlogn)。

三：归并排序的实现

package Study.paixu;

import java.util.Arrays;

/**
 * 归并排序
 */
public class gbpx {
    public static void main(String[] args) {
        int []px = {1,2,5,7,6,8,3,4};
        sort(px);
        System.out.println(Arrays.toString(px));
    }

    public static void sort(int[] arr){
        int[] temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }

    public 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);
            merege(arr,left,mid,right,temp);
        }
    }

    public static void merege(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[t++] = arr[i++];
        }
        while(j<=right){
            temp[t++] = arr[j++];
        }

        t = 0;
        
        while(left <= right){
            arr[left++] = temp[t++];
        }

    }
}

image.png