常见排序介绍及优化手段

1.插入排序

public static void main(String[] args) {
    int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
    //插入排序：每次将当前元素插入到左侧已经排好的数组中
    int len=arr.length;
    for (int i = 1; i < len; i++) {
        for (int j = i; j >0; j--) {
            if(arr[j]<arr[j-1]){
                int tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

2. 堆排序

public class duipaixu {
    public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //插入排序：每次将当前元素插入到左侧已经拍好的数组中
        int len=arr.length;
        heap_sort(arr,len-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void heap_sort(int[] arr,int len){
        //形成二叉堆
        for (int i = (len-2)/2; i >=0; i--) {
            downadjust(arr,i,len+1);
        }
        for(int i=len;i>0;i--){
            int tmp=arr[i];
            arr[i]=arr[0];
            arr[0]=tmp;
            downadjust(arr,0,i);
        }
    }

    private static void downadjust(int[] arr,int parent,int len){
        int tmp=arr[parent];
        int child=2*parent+1;
        while(child<len){
            if(child+1<len&&arr[child]>=arr[child+1]){
                child++;
            }
            if(tmp<=arr[child]){
                break;
            }
            arr[parent]=arr[child];
            parent=child;
            child=2*parent+1;
        }
        arr[parent]=tmp;
    }
}

3. 归并排序

public class guibinpaixu {

    public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //插入排序：每次将当前元素插入到左侧已经拍好的数组中
        int len=arr.length;
        gbsort(arr,0,len-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void gbsort(int[] arr,int l,int r){
        if(l>=r){
            return;
        }
        int mid=l+(r-l)/2;
        gbsort(arr,l,mid);
        gbsort(arr,mid+1,r);
        help(arr,l,mid,r);
    }
    private static void help(int[] arr,int l,int mid,int r){
        int[] help=new int[r-l+1];
        int p=l;
        int q=mid+1;
        int index=0;
        while(p<=mid&&q<=r){
            help[index++]=arr[p]<arr[q]?arr[p++]:arr[q++];
        }
        while(p<=mid){
            help[index++]=arr[p++];
        }
        while(q<=mid){
            help[index++]=arr[q++];
        }
        for(int i=0;i<index;i++){
            arr[i+l]=help[i];
        }
    }
}

4. 快速排序

public class kuaipai {
    public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //插入排序：每次将当前元素插入到左侧已经拍好的数组中
        int len=arr.length;
        quick_sort(arr,0,len-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void quick_sort(int[] arr,int l ,int r){
        if(l>=r){
            return;
        }
        int index=partition(arr,l,r);
        quick_sort(arr,l,index-1);
        quick_sort(arr,index+1,r);
    }

    private static int partition(int[] arr,int l ,int r){
        int tmp=arr[l];
        while(l<r){
            while(l<r&&arr[r]>=tmp){
                r--;
            }
            arr[l]=arr[r];
            while (l<r&&arr[l]<=tmp){
                l++;
            }
            arr[r]=arr[l];
        }
        arr[l]=tmp;
        return l;
    }
}
``````

##### 5. 冒泡排序

```java
public static void main(String[] args) {
    int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
    //每次冒泡出一个结果到最后
    int len=arr.length;
    for(int i=len-2;i>=0;i--){
        for(int j=0;j<=i;j++){
            if(arr[j]>arr[j+1]){
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

6. 希尔排序

public static void main(String[] args) {
    int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
    //插入排序：每次将当前元素插入到左侧已经拍好的数组中
    int len=arr.length;
    int h=1;
    while(h<len/3){
        h=h*3+1;
    }
    while(h>=1){
        for(int i=h;i<len;i++){
            for(int j=i;j>=h;j-=h){
                if(arr[j]<arr[j-h]){
                    int tmp=arr[j];
                    arr[j]=arr[j-h];
                    arr[j-h]=tmp;
                }
            }
        }
        h/=3;
    }
    System.out.println(Arrays.toString(arr));
}

7. 选择排序

public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //选择排序，每次选择一个最小的与前面的交换
        int len=arr.length;
        for (int i = 0; i < len-1; i++) {
            int min=i;
            for (int j = i+1; j <len ; j++) {
                if(arr[min]>arr[j]){
                    min=j;
                }
            }
            int tmp=arr[min];
            arr[min]=arr[i];
            arr[i]=tmp;
        }
        System.out.println(Arrays.toString(arr));
    }

各大排序优化：
冒泡：加入一个flag，如果有一轮flag没变说明没排序，说明已经排序好，可以直接退出
快排：小数组切换到插入排序，三数取中，三向切分
三向切分：类似于荷兰国旗改进，荷兰国旗问题和经典快排不同的就只是将<=num改为了< num和=num两部分，借用这个思想使得原来每次只可以让一个数找到正确的位置改进为了每次至少让一个数找到位置 在topk问题中，快排每次可以排除一半元素
随机快排 1. 选取最后一个数：如果是一个已经排好序的数组，每次找到位置之后，左边是要进行排序的部分，数组长度是原长度-1，它的时间复杂度就是O(N^2)；如果每次找到的数都是中间的位置，它的时间复杂度就只有O(logN) 2. 然而以随机数作为选取的标准num的时候，因为是随机的，就只能通过数学期望去计算它的时间复杂度，时间复杂度是O(logN)