Java中的七大排序（上）

一般排序通常認為是升序。
穩(wěn)定性：兩個相等的數(shù)據(jù)若在排序前后的相對位置不發(fā)生改變，則稱該算法是具備穩(wěn)定性的算法。
一：插入排序
原理：將數(shù)組分為有序區(qū)間和無序區(qū)間，每次用無需區(qū)間的
第一個數(shù)與有序區(qū)間進行比較。
時間復雜度：O(n*n),空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
代碼如下：

站在用戶的角度思考問題，與客戶深入溝通，找到電白網(wǎng)站設計與電白網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設計與互聯(lián)網(wǎng)技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都做網(wǎng)站、成都網(wǎng)站設計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、國際域名空間、網(wǎng)站空間、企業(yè)郵箱。業(yè)務覆蓋電白地區(qū)。

public static void insertSort0(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 有序區(qū)間  [0, i)
            // 無序區(qū)間  [i, array.length)
            int key = array[i];
            int j;
            for (j = i - 1; j >= 0 && array[j] > key; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = key;
        }
    }

二：希爾排序
原理：分組插排，每分隔gap個大小從數(shù)組中取一個數(shù)，進而將數(shù)組分成了若干個組，重復此操作，直到gap=1；
時間復雜度：O(n)~O(n*n),空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
代碼如下：

public static void shellSort(int[] array){
    int gap=array.length;
    while(true){
        gap=(gap/3)+1;//or gap=gap/2
        insertSortWithGap(array,gap);
        if(gap==1){
            break;
        }
    }
}
private static void inserSortWithGap(int[] array,int gap){
    for(int i=gap;i<array.length;i++){
        int key=array[i];
        int j;
        for(j=i-gap;j>=0&&array[j]>key;j-=gap){
            array[j+gap]=array[j];
        }
        array[j+gap]=key;
    }
}

三：選擇排序
1.單向選擇排序
原理：每次從無序區(qū)間選出最大(或者最小)的數(shù)存放在無序區(qū)間的最后（最前），直到所有的待排序數(shù)據(jù)排序完。
時間復雜度：O(n^2),空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定

public static void selsctSort1(int[] array){
    //每次選最小的放在無序區(qū)間的前面
    for(int i=0;i<array.length-1;i++){//需要排序的次數(shù)
        //有序：[0,i)
        //無序：[i,array.length)
        int minIndex=i;
        for(int j=i+1;j<array.length;j++){
            if(array[j]<array[minIndex]){
                minIndex=j;
            }
        }
        swap(array,mindex,i);
    }
}
public static void selsctSort2(int[] array){
    //每次選最大的放在無序區(qū)間的后面
    for(int i=0;i<=array.length-1;i++){
        //無序：[0,array.length-i)
        //有序：[array.length-i,array.length)
        int maxIndex=0;
        for(int j=1;j<array.length-i;j++){
            if(array[j]>array[max]){
                max=j;
            }
        }
        int t=array[max];
        array[max]=array[array.length-i-1];
        array[array.length-i-1]=t;
    }

2.雙向排序比較
     原理：每一次從無序區(qū)間選出最小 + 最大的元素，存放在無序區(qū)間的最前和最后，直到全部待排序的數(shù)據(jù)元素排完 。
     時間復雜度：O(n^2),空間復雜度：O(1)
     穩(wěn)定性：不穩(wěn)定

代碼如下：

public static void selectSort3(int[] array){
    int low=0;
    int high=array.length-1;
    //[low,high]表示整個無序區(qū)間
    while(low<=high){
        int min=low;
        int high=low;
        for(int i=low+1;i<=max;i++){
        if (array[i] < array[min]) {
             min = i; 
        }
        if (array[i] > array[max]) {
             max = i; 
        }
        swap(array, min, low);
        if (max == low) {
             max = min; 
        }
        swap(array, max, high);
        }
        private void swap(int[] array, int i, int j) {
             int t = array[i]; array[i] = array[j]; array[j] = t;       
        }  
}

分享文章：Java中的七大排序（上）
標題來源：http://bm7419.com/article24/jdeoje.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供響應式網(wǎng)站、App設計、營銷型網(wǎng)站建設、ChatGPT、網(wǎng)站設計、全網(wǎng)營銷推廣

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容