前言

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

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

結(jié)果在希爾排序移位法的第3點(diǎn)中 , 可以直接跳轉(zhuǎn)查看

下面將介紹這幾種排序方式及其同異點(diǎn)

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

一、直接插入排序

1. 圖解插排

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

圖解 :

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

根據(jù)上述的思路 ,我們需要將序列劃分為兩部分, 為了編碼方便,我們將第一個元素假設(shè)為有序集合, 那么我們的循環(huán)應(yīng)當(dāng)是從第2個元素開始的,也就是3

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

由于是對數(shù)組繼進(jìn)行操作 , 我們同時也需要獲取有序集合的最后一個元素的索引作為游標(biāo)

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

上圖由于集合內(nèi)只有一個4, 游標(biāo)前移越界了, 因此循環(huán)終止. 下一輪比較開始執(zhí)行

2. 代碼實(shí)現(xiàn)

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

3.性能檢測與時空復(fù)雜度

實(shí)際運(yùn)行80w個數(shù)據(jù)耗時1分4秒(非準(zhǔn)確值,每臺機(jī)器可能都不一樣)

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

時間復(fù)雜度 :

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

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

二、希爾排序(交換法)

1. 思路圖解

2. 代碼實(shí)現(xiàn)

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++){ //先遍歷所有數(shù)組
                for(int j  = i - gap ; j >= 0 ; j -= gap){//開啟插入排序
                    if(arr[ j ] > arr[ gap + j ]){ //可以根據(jù)升降序修改大于或小于
                        tmp = arr[gap + j];
                        arr[j+gap] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            System.out.println(gap);
            System.out.println(Arrays.toString(arr));
        }
    }
12345678910111213141516

這里最難理解的應(yīng)該是第三個for循環(huán),j = i - gap, 表示小組內(nèi)的第一個元素,即j=0,

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

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

3. 時間復(fù)雜度

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

4. 關(guān)于增量的選擇

上述我們在做排序的時候增量縮減選用的時gap/=2的模型, 這并不是最優(yōu)的選擇 , 關(guān)于增量的選取 , 屬于數(shù)學(xué)界尚未解決的一個問題

但是可以確定的是, 通過大量的實(shí)驗(yàn)證明 ,當(dāng)n->無窮大時, 時間復(fù)雜度可以減少到 :

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

三、希爾排序(移位法)

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

1. 思路

思路其實(shí)就是上述兩種排序的結(jié)合 , 將分組 與 插入的優(yōu)點(diǎn)結(jié)合到一起, 效率非常高

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

2. 代碼實(shí)現(xiàn)

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]){ //插入的值小于組內(nèi)另一個值
                   while(valIndex - gap >=0 && val < arr[valIndex-gap]){ //開始插排
                       // 插入
                       arr[valIndex] = arr[valIndex-gap];
                       valIndex -= gap; //讓valIndex = valIndex-gap (游標(biāo)前移)
                   }
                }
                arr[valIndex] = val;
            }
        }
    }
12345678910111213141516

3. 實(shí)驗(yàn)結(jié)果

總結(jié)

到此這篇關(guān)于Java算法實(shí)戰(zhàn)之排一億個隨機(jī)數(shù)的文章就介紹到這了,更多相關(guān)Java一億個隨機(jī)數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論