归并排序

class Solution {    public int[] sortArray(int[] nums) {        int n=nums.length;        mergeSort(nums,0,n-1);        return nums;    }     //进行归并操作，对于两个数组分别为arr[l,mid]和arr[mid+1,r]进行归并。i,j分别指向aux对应于左边和右边的数组，而k指向要归并的数组，即原数组。    public static void merge(int[] arr,int l,int mid,int r){        int[] aux=new int[r-l+1];        for(int i=l;i<=r;i++)        {            aux[i-l]=arr[i];        }        int i=l,j=mid+1;        for(int k=l;k<=r;k++)        {            if(i>mid)            {                arr[k]=aux[j-l];                j++;            }            else if(j>r)            {                arr[k]=aux[i-l];                i++;            }            else  if(aux[i-l]<aux[j-l])            {                arr[k]=aux[i-l];                i++;            }            else {                arr[k]=aux[j-l];                j++;            }        }            }    //进行划分操作，递归地将数组分开成两半，一直分到只剩一个，就return；，然后对于递归的数组每个层次都进行一个归并，最底层两个数组分别只有一个元素    public static void mergeSort(int[] arr,int l,int r)    {        if(l>=r)        {            return;        }        int mid=(l+r)/2;        mergeSort(arr,l,mid);        mergeSort(arr,mid+1,r);        if(arr[mid]>arr[mid+1])        {            merge(arr,l,mid,r);        }            }}

转载于:https://www.cnblogs.com/cold-windy/p/11184391.html

相关资源：归并排序 C语言实现