排序算法实现【选择、插入、希尔、归并】

每次遍历选择最小的往前排

    public int[] sort(int []a){
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i+1; j < a.length; j++) {
                if(sortMain.less(a[i],a[j])){
                    min = j;
                }
            }
            sortMain.exch(a,i,min);
        }
        return a;
    }


    //比较
    public boolean less(int a,int b){
        return a>b;
    }
    //交换
    public void exch(int []array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

每次遍历与前面已经排好的有序排练进行对比，不断的交换，插入到合适的位置

    public void sort(int []a){
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int tmp = a[i];
            for (int j = i-1; j >=0; j--) {
                if(a[j]>tmp){
                    a[j+1] = a[j];
                    a[j]=tmp;
                }else {
                    a[j+1] = tmp;
                    break;
                }
            }
        }
    }

插入排序的变种，增加希尔增量用于排成局部有序的状态（插入排序），最后增量为1时和插入排序时一样的，这样做减少了交换的次数。

    public int[] sort(int[] a) {
        int n = 1;
        int size = a.length;
        //希尔增量
        while (n > size / 3) {
            n = n * 3 + 1;
        }
        while (n >= 1) {
            for (int i = n; i < size; i++) {
                for (int j = i; j >= n && a[j] < a[j - n]; j -= n) {
                    int tmp = a[j];
                    a[j] = a[j - n];
                    a[j - n] = tmp;
                }
            }
            n /= 3;
        }
        return a;
    }

根据start-end进行拆分，分别排序各个子序列，最后归并子序列完成排序

package leetcode.May;


public class MergesSort {
    static SortMain sortMain = new SortMain();

    
    public int []tmp;
    public int[] sort(int []a){
        int n = a.length;
        //临时数组
        tmp = new int[n];
        marges(a,0,n-1);
        return a;
    }

    
    public void marges(int []a,int start,int end){
        if(start==end){
            return;
        }
        int mid = start+(end-start)/2;
        int l = start;
        int r = mid+1;
        marges(a,l,mid);
        marges(a,r,end);
        int index = start;
        for (int i = start; i <= end; i++) {
            if(r>end){
                tmp[index++] = a[l++];
            }else if(l>mid){
                tmp[index++]=a[r++];
            }else if(a[l]>a[r]){
                tmp[index++]=a[r++];
            }else {
                tmp[index++]=a[l++];
            }
        }
        for (int i = start; i <= end; i++) {
            a[i] = tmp[i];
        }
    }




    public static void main(String[] args) {
        MergesSort MergesSort = new MergesSort();
        int[] a = new int[]{2, 3, 1,4,7,5,10,9,6};
        sortMain.show(MergesSort.sort(a));
    }
}