[Java知识库]归并排序（数组和链表java）

归并排序

1. 利用分治和递归的思想，先分，后并
   java代码

public class Tset {
    public static void main(String[] args) {
        int[] arr = new int[]{4,6,7,1,2,8,5};

        mergeSort(arr);
        for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
        }

    }

    private static void mergeSort(int[] arr){
        mergeSortInertal(arr,0,arr.length-1);
    }
    private static void mergeSortInertal(int[] arr,int low,int high){
        if (low >= high) return;

        int mid = (low+high)>>>1;

        mergeSortInertal(arr,low,mid);
        mergeSortInertal(arr,mid+1,high);

        merge(arr,low,mid,high);
    }
    private static void merge(int[] arr,int low,int mid,int high){
        int s1 = low;
        int s2 = mid+1;
        int [] ret = new int[high-low+1];

        int i = 0;
        while (s1 <= mid && s2 <= high){
           if (arr[s1] < arr[s2]){
               ret[i++] = arr[s1++];
           }else{
               ret[i++] = arr[s2++];
           }
        }

        while (s1 <=mid){
            ret[i++] = arr[s1++];
        }
        while (s2 <= high){
            ret[i++] = arr[s2++];
        }
        for (int j = 0; j < ret.length; j++) {
            arr[low+j] = ret[j];
        }

    }
}

链表归并排序

 public static ListNode sortList(ListNode head) {
        ListNode cur = head;
        while(cur.next != null && cur != null){
            cur = cur.next;
        }
        return sortList(head,cur);

    }
    public static ListNode sortList(ListNode head,ListNode end) {
        if(head == null ) return head;
        if (head.next == end){
            head.next = null;
            return head;
        }
        ListNode low = head,fast = head;
        while(fast != end){
            low = low.next;
            fast = fast.next;
            if(fast != end){
                fast = fast.next;
            }
        }
        ListNode mid = low;
        ListNode m1 = sortList(head,mid);
        ListNode m2 = sortList(mid,end);

        return   merge(m1,m2);

    }



    private static ListNode merge(ListNode m1,ListNode m2){
        ListNode newTmp = new ListNode(0);
        ListNode tmp1 = m1;
        ListNode tmp2 = m2;

        ListNode tmp = newTmp;
        while(tmp1 != null && tmp2 != null){
            if(tmp1.val < tmp2.val ){
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            }else{
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if(tmp1 != null){
            tmp.next = tmp1;
        }else if(tmp2 != null){
            tmp.next = tmp2;
        }

        return newTmp.next;



    }