Java如何排一億個隨機數

這篇文章主要介紹Java如何排一億個隨機數，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

一、直接插入排序

1. 圖解插排

思路 : 字面意義,插入是將某一元素按某種規則放入到特定集合中 ,因此我們需要將序列劃分成為兩塊 ,一部分為有序集合, 另一部分為待排序集合

圖解 :

為了方便理解,我們就按最最最特殊的4321序列來舉例,

根據上述的思路 ,我們需要將序列劃分為兩部分, 為了編碼方便,我們將第一個元素假設為有序集合, 那么我們的循環應當是從第2個元素開始的,也就是3

為避免后面操作把3覆蓋掉了 , 我們選擇一個臨時變量來保存3.也就是上文的 val=arr[1] ,

由于是對數組繼進行操作 , 我們同時也需要獲取有序集合的最后一個元素的索引作為游標

當游標不越界 , 且待插入的值小于游標指示位置時(上圖的4<3) , 我們將元素4后移 , 游標前移,繼續檢查集合中的其它元素是否也小于待插入的元素, 直到游標越界

上圖由于集合內只有一個4, 游標前移越界了, 因此循環終止. 下一輪比較開始執行

2. 代碼實現

public static void insertSort(int[]arr){
        for(int i = 1 ; i < arr.length; i++){
            int val = arr[i];
            int valIndex = i - 1; //游標
            while(valIndex >= 0 && val < arr[valIndex]){ //插入的值比游標指示的值小
                arr[valIndex + 1] = arr[valIndex];
                valIndex--; //游標前移
            }
            arr[valIndex+1] = val;
        }
    }
1234567891011

3.性能檢測與時空復雜度

實際運行80w個數據耗時1分4秒(非準確值,每臺機器可能都不一樣)

直接插排在排序記錄較少, 關鍵字基本有序的情況下效率較高

時間復雜度 :

關鍵字比較次數 : KCN=(n^2)/2 總移動次數 : RMN= (n^2)/2

因此時間復雜度約為 O(N^2)

二、希爾排序(交換法)

1. 思路圖解

2. 代碼實現

public static void shellSort(int[] arr){ //交換法
        int tmp = 0;
        for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2){
            for(int i = gap ; i < arr.length ; i++){ //先遍歷所有數組
                for(int j  = i - gap ; j >= 0 ; j -= gap){//開啟插入排序
                    if(arr[ j ] > arr[ gap + j ]){ //可以根據升降序修改大于或小于
                        tmp = arr[gap + j];
                        arr[j+gap] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            System.out.println(gap);
            System.out.println(Arrays.toString(arr));
        }
    }
12345678910111213141516

這里最難理解的應該是第三個for循環,j = i - gap, 表示小組內的第一個元素,即j=0,

當小組內的第一個元素大于第二個元素時(由于是邏輯上的分類,第二個元素的索引應當是第一個元素的所有值+增量gap) , 交換兩者,反之j-=gap,繼續比較或跳出循環 ,

如此往復將所有小組都遍歷完之后 , 縮小增量(即gap/=2) , 然后繼續上述步驟, 直到增量gap為1時, 序列排序結束

3. 時間復雜度

希爾排序的時間復雜度取決于增量序列的函數 , 需要具體問題具體分析,并不是一個確定的值,這也是第四點需要討論的問題

4. 關于增量的選擇

上述我們在做排序的時候增量縮減選用的時gap/=2的模型, 這并不是最優的選擇 , 關于增量的選取 , 屬于數學界尚未解決的一個問題

但是可以確定的是, 通過大量的實驗證明 ,當n->無窮大時, 時間復雜度可以減少到 :

在下一點, 移位法中 , 我們也做了幾個實驗 , 可以肯定的時,對于一定規模內(如800w~1億) 的計算, 希爾排序的速度遠遠超過了堆排序, 至少在筆者的電腦上是這樣的

三、希爾排序(移位法)

交換法的速度比移位法慢很多 ,因此更多的是使用地移位法,并且移位法相較于交換法, 更"像"插入排序

1. 思路

思路其實就是上述兩種排序的結合 , 將分組 與 插入的優點結合到一起, 效率非常高

體現的就是分治的思路,將一個較大序列切割成若干較小序列

2. 代碼實現

public static void shellSort02(int[] arr){ //移位法
        for(int gap = arr.length/2 ; gap > 0 ; gap /= 2){ //分組
            for(int i = gap ; i < arr.length ; i++){ //遍歷
                int valIndex = i;
                int val = arr[valIndex];
                if(val < arr[valIndex-gap]){ //插入的值小于組內另一個值
                   while(valIndex - gap >=0 && val < arr[valIndex-gap]){ //開始插排
                       // 插入
                       arr[valIndex] = arr[valIndex-gap];
                       valIndex -= gap; //讓valIndex = valIndex-gap (游標前移)
                   }
                }
                arr[valIndex] = val;
            }
        }
    }
12345678910111213141516

3. 實驗結果

以上是“Java如何排一億個隨機數”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！