Java實現(xiàn)的各種排序算法

import java.util.Arrays;

public class AllSort {
    public static void main(String[] args){
        int[] arr={2,9,3,6,1,0,1};
        //selectSort(arr);
        //bubbleSort(arr);
        //insertSort(arr);
        //shellSort(arr);
        //shellSort2(arr);
        //mergeSort(arr);
        //quickSort(arr);
        heapSort(arr);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    
    // 最好的情況：正序，交換0次，比較O(n^2)
    // 最壞的情況：交換n-1次，比較O(n^2) 
    // 平均O(n^2)
    // 不穩(wěn)定 eg：5 6 5 2 原來相等的數(shù)據(jù)排序后交換了順序
    // 空間復雜度O(1)
    public static void selectSort(int[] arr){
        if(arr==null || arr.length ==0){
            return;
        }
        for(int i=0;i<arr.length;i++){
            int minIndex=i;
            for(int j=i;j<arr.length;j++){
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            swap(arr,i,minIndex);
        }
    }
    
    //最好的情況：正序，比較n-1次，交換0次，復雜度O(n)
    //最壞的情況：逆序，交換O(n^2)，比較O(n^2)
    //平均：O(n^2)
    //穩(wěn)定的
    //空間O(1)
    public static void bubbleSort(int[] arr){
        if(arr==null || arr.length==0){
            return;
        }
        boolean isSwap=false;
        for(int i=arr.length-1;i>=0;i--){
            isSwap=false;
            for(int j=0;j<i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr, j, j+1);
                    isSwap=true;
                }
            }
            if(!isSwap) return;
        }
    }
    
    //最好的情況：正序，比較n-1次，移動0次，復雜度O(n)
    //最壞的情況：逆序，交換O(n^2)，移動O(n^2)，復雜度O(n^2)
    //平均：O(n^2)
    //穩(wěn)定的
    //空間O(1)
    public static void insertSort(int[] arr){
        if(arr==null || arr.length ==0){
            return;
        }
        for(int i=1;i<arr.length;i++){
            int key=arr[i];
            int j=i;
            while (--j>=0 && arr[j]>key) {
                arr[j+1]=arr[j];
            }
            arr[j+1]=key;
        }
    }
    
    /*改進的插入排序算法
     *eg：主鍵最小的元素在最后面，則將它移動到正確位置需要移動n-1次
     *希爾排序是為了改進插入排序，交換不相鄰的元素以對數(shù)組的局部進行排序，
     *并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。
     *把記錄按下標的一定增量分組，對每一組數(shù)據(jù)使用插入排序，
     *一個h有序數(shù)組則是h個有序子數(shù)組組成的，
     *隨著增量逐漸減少每組包含的關鍵詞越來越多，
     *當增量減至1時，整個文件恰被分成一組，算法便終止。
    */
    //最好 O(n^s)，最壞O(n^s)，實際復雜度和增量序列有關，
    //s[1,2]之間，取決于增量序列，一般最好O(n^1.3)
    //shell在排好序的情況下比插入排序要差的
    //eg：1234，插入比較3次，shell，d=2，[1,3][2,4]比較2次，
    //然后d=d/2=1[1,2,3,4]比較3次，總共比較5次
    public static void shellSort(int[] arr){
        if(arr==null ||arr.length==0){
            return;
        }
        int N=arr.length;
        int h=1;
        while(h < N/3) h=3*h+1;//1,4,13,40,121,...
        while (h >= 1) {
            //將數(shù)組變?yōu)閔有序
            for (int i = h; i < N; i++) {
                //將a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...通過交換相鄰元素法
                for(int j=i;j>=h&&arr[j]<arr[j-h];j-=h){
                    swap(arr, j, j-h);
                }
            }
            h=h/3;
        }
    }
    //移動數(shù)組法
    public static void shellSort2(int[] arr){
        if(arr==null ||arr.length==0){
            return;
        }
        int N=arr.length;
        int gap=1;
        while(gap < N/3) gap=3*gap+1;//1,4,13,40,121,...
        while(gap>=1){
            for(int i=gap;i<arr.length;i++){
                int key=arr[i];
                int j=i;
                while(j-gap>=0 && arr[j-gap]>key){
                    arr[j]=arr[j-gap];
                    j-=gap;
                }
                arr[j]=key;
            }
            gap=gap/3;
        }
        
    }
    
    //最好&最壞&平均O(nlogn)，空間O(n)，穩(wěn)定的
    public static void mergeSort(int[] arr){
        if(arr==null || arr.length==0){
            return;
        }
        mergeSort(arr,0,arr.length-1);
    }
    private static void mergeSort(int[] arr,int lo,int hi){
        if(lo>=hi){
            return;
        }
        int mid=(lo+hi)>>1;
        mergeSort(arr,lo,mid);
        mergeSort(arr,mid+1,hi);
        merge(arr,lo,mid,hi);
    }
    private static void merge(int[] arr,int lo,int mid,int hi){
        int[] left=Arrays.copyOfRange(arr, lo, mid+1);
        int[] right=Arrays.copyOfRange(arr, mid+1, hi+1);
        int i=0,j=0,k=lo;
        while (i<left.length && j<right.length) {
            if(left[i]<right[j]){
                arr[k++]=left[i++];
            }
            else{
                arr[k++]=right[j++];
            }
        }
        while(i<left.length){
            arr[k++]=left[i++];
        }
        while(j<right.length){
            arr[k++]=right[j++];
        }
    }
    
    
    //正序和逆序的情況都是最差的，每次迭代只減少一個元素O(n^2)
    //最好的情況，每次切分的元素正確位置都于序列的中間，O(nlogn)
    //平均O(nlogn)，為了避免最壞的情況可以進行shuffle
    //空間O(1)
    //不穩(wěn)定
    public static void quickSort(int[] arr){
        if(arr==null || arr.length==0){
            return ;
        }
        quickSort(arr,0,arr.length-1);
    }
    private static void quickSort(int[] arr,int lo,int hi){
        if(lo>=hi){
            return;
        }
        int j=partition(arr,lo,hi);
        quickSort(arr, lo, j-1);
        quickSort(arr, j+1, hi);
    }
    private static int partition(int [] arr,int lo,int hi){
        int i=lo;
        int key=arr[lo];
        int j=hi+1;
        while (true) {
            while (arr[++i]<key) {
                if(i==hi) break;
            }
            while (arr[--j]>key) {
                if(j==lo) break;
            }
            if(i>=j) break;
            swap(arr, i, j);
        }
        swap(arr, lo, j);
        return j;
    }
    
    
    //建堆O(n)，最好，最壞，平均nlogn，空間O(1)
    public static void heapSort(int[] arr){
        if(arr==null||arr.length==0){
            return;
        }
        for(int i=(arr.length-1)/2;i>=0;i--){
            adjustMaxHeap(arr,i,arr.length);
        }
        for (int i = arr.length-1; i >= 0; i--) {
            swap(arr, i, 0);
            adjustMaxHeap(arr, 0, i);
        }
    }
    private static void adjustMaxHeap(int[] arr,int i,int lastIndex){
        int left=2*i+1;
        int right=2*i+2;
        int maxIndex=i;
        if(left <lastIndex &&arr[left] >arr[maxIndex]){
            maxIndex=left;
        }
        if(right<lastIndex && arr[right] >arr[maxIndex]){
            maxIndex=right;
        }
        if(i != maxIndex){
            swap(arr, maxIndex, i);
            adjustMaxHeap(arr, maxIndex, lastIndex);
        }
    }
}
最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容