java实现归并排序和快速排序

归并排序

原理：将一个数组通过递归的方法分成无数小数组 将数组排序后然后合并成一个大数组 merge 为数组合并方法

import java.util.Arrays;

public class mergeStort {
    private mergeStort() {};
    public static <E extends Comparable <E>> void sort(E[] arr) {
        sort(arr,0, arr.length-1);
    }
    private static <E extends Comparable <E>> void sort(E[] arr, int l , int r) {
        if( l >= r) return ;
        int mid = (l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    // 归并方法 : 合并两个有序的区间 arr[i,mid] 和 arr [mid+1,r]
    private static  <E extends  Comparable <E>> void merge(E[] arr, int l ,int mid ,int r){
        E[] temp = Arrays.copyOfRange(arr,l,r+1);
        int i =l , j = mid + 1;
//        每轮循环为 arr[k] 赋值
        for(int k = l ; k <= r ; k++){
//arr[i] 和 arr[j]
            if(i > mid) {
                arr[k] = temp[j - l];
                j++;
            }else if(j > r) {
                arr[k] = temp[i - l];
                i++;
            }else if(temp[i -l].compareTo(temp[j - l]) <= 0){
                arr[k] = temp[i -l ];
                i++;
            }else {
                arr[k] = temp[j-l];
                j++;
            }
        }
    }
}

快速排序

1.找一个基点 左侧是小于这个基点的数据 右侧是大于基点的数据通过将左侧 Partition 方法是找基点的方法。

        sort(arr,0,arr.length-1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr ,int l ,int r) {
        if(l >= r) return;
        int p = Partition(arr,l,r);
        sort(arr,l,p-1);
        sort(arr,p+1,r);
    }
    private static <E extends Comparable<E>> int Partition(E[] arr,int l, int r) {
        //arr[l+1 ... j] < v ；arr[j+1 ... i] > v
        int j = l;
        for(int i = l +1;i<=r;i++) {
            if(arr[i].compareTo(arr[l] ) < 0) {
                j++;
                swap(arr ,i ,j);
            }
        }
        swap(arr,l,j);
        return j;
    }
    public static <E> void swap(E[]arr,int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}