搜尋
首頁Javajava教程如何用Java對一億個隨機數字進行排序?

一、直接插入排序

1. 圖解插排

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

圖解:

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

為了方便理解,我們就按最最特殊的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秒(非準確值,每台機器可能都不一樣)

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

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

時間複雜度:

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

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

二、希爾排序(交換法)

1. 思路圖解

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

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->無窮大時, 時間複雜度可以減少到:

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

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

三、希爾排序(移位法)

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

#1. 思路

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

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

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

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對一億個隨機數字進行排序?
如何用Java對一億個隨機數字進行排序?

以上是如何用Java對一億個隨機數字進行排序?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文轉載於:亿速云。如有侵權,請聯絡admin@php.cn刪除
為什麼Java是開發跨平台桌面應用程序的流行選擇?為什麼Java是開發跨平台桌面應用程序的流行選擇?Apr 25, 2025 am 12:23 AM

javaispopularforcross-platformdesktopapplicationsduetoits“ writeonce,runany where”哲學。 1)itusesbytiesebyTecodeThatrunsonAnyJvm-備用Platform.2)librarieslikeslikeslikeswingingandjavafxhelpcreatenative-lookingenative-lookinguisis.3)

討論可能需要在Java中編寫平台特定代碼的情況。討論可能需要在Java中編寫平台特定代碼的情況。Apr 25, 2025 am 12:22 AM

在Java中編寫平台特定代碼的原因包括訪問特定操作系統功能、與特定硬件交互和優化性能。 1)使用JNA或JNI訪問Windows註冊表;2)通過JNI與Linux特定硬件驅動程序交互;3)通過JNI使用Metal優化macOS上的遊戲性能。儘管如此,編寫平台特定代碼會影響代碼的可移植性、增加複雜性、可能帶來性能開銷和安全風險。

與平台獨立性相關的Java開發的未來趨勢是什麼?與平台獨立性相關的Java開發的未來趨勢是什麼?Apr 25, 2025 am 12:12 AM

Java將通過雲原生應用、多平台部署和跨語言互操作進一步提昇平台獨立性。 1)雲原生應用將使用GraalVM和Quarkus提升啟動速度。 2)Java將擴展到嵌入式設備、移動設備和量子計算機。 3)通過GraalVM,Java將與Python、JavaScript等語言無縫集成,增強跨語言互操作性。

Java的強鍵入如何有助於平台獨立性?Java的強鍵入如何有助於平台獨立性?Apr 25, 2025 am 12:11 AM

Java的強類型系統通過類型安全、統一的類型轉換和多態性確保了平台獨立性。 1)類型安全在編譯時進行類型檢查,避免運行時錯誤;2)統一的類型轉換規則在所有平台上一致;3)多態性和接口機制使代碼在不同平台上行為一致。

說明Java本機界面(JNI)如何損害平台獨立性。說明Java本機界面(JNI)如何損害平台獨立性。Apr 25, 2025 am 12:07 AM

JNI會破壞Java的平台獨立性。 1)JNI需要特定平台的本地庫,2)本地代碼需在目標平台編譯和鏈接,3)不同版本的操作系統或JVM可能需要不同的本地庫版本,4)本地代碼可能引入安全漏洞或導致程序崩潰。

是否有任何威脅或增強Java平台獨立性的新興技術?是否有任何威脅或增強Java平台獨立性的新興技術?Apr 24, 2025 am 12:11 AM

新興技術對Java的平台獨立性既有威脅也有增強。 1)雲計算和容器化技術如Docker增強了Java的平台獨立性,但需要優化以適應不同雲環境。 2)WebAssembly通過GraalVM編譯Java代碼,擴展了其平台獨立性,但需與其他語言競爭性能。

JVM的實現是什麼,它們都提供了相同的平台獨立性?JVM的實現是什麼,它們都提供了相同的平台獨立性?Apr 24, 2025 am 12:10 AM

不同JVM實現都能提供平台獨立性,但表現略有不同。 1.OracleHotSpot和OpenJDKJVM在平台獨立性上表現相似,但OpenJDK可能需額外配置。 2.IBMJ9JVM在特定操作系統上表現優化。 3.GraalVM支持多語言,需額外配置。 4.AzulZingJVM需特定平台調整。

平台獨立性如何降低發展成本和時間?平台獨立性如何降低發展成本和時間?Apr 24, 2025 am 12:08 AM

平台獨立性通過在多種操作系統上運行同一套代碼,降低開發成本和縮短開發時間。具體表現為:1.減少開發時間,只需維護一套代碼;2.降低維護成本,統一測試流程;3.快速迭代和團隊協作,簡化部署過程。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中