如何用Java對一億個隨機數字進行排序？

一、直接插入排序

1. 圖解插排

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

圖解:

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

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

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

由於是對陣列繼進行運算, 我們同時也需要取得有序集合的最後一個元素的索引作為遊標

當遊標不越界 , 且待插入的值小於遊標指示位置時(上圖的4) , 我們將元素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對一億個隨機數字進行排序？的詳細內容。更多資訊請關注PHP中文網其他相關文章！