Java算法實戰之排一億個隨機數

Posted on by

前言

插入排序狹義上指的是簡單插入排序(選擇集合,比較大小,插入元素),廣義上還應該包括希爾排序(分治思想)及其兩種實現方式,

最激動人心的是 , 希爾排序(移位法)的效率奇高, 在本地調試中,一億 個隨機數僅需30S即可排完 (不同機器可能結果不同) ,在數據量較大時效率是比堆排序要高的

結果在希爾排序移位法的第3點中 , 可以直接跳轉查看

下面將介紹這幾種排序方式及其同異點

提示：以下是本篇文章正文內容，下面案例可供參考

一、直接插入排序

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算法實戰之排一億個隨機數的文章就介紹到這瞭,更多相關Java一億個隨機數內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：