插入排序（穩(wěn)定）

假設(shè)有這樣一個數(shù)組，想要從小到大進行排序：

int[] array = {4,9,5,8,6,2,10,7,3,1};

插入排序代碼實現(xiàn)：

public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int ret = arr[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if(arr[j] > ret) {
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = ret;
                    break;
                }
            }
            arr[j+1] = ret;
        }
    }

代碼運行結(jié)果：

可以看到，結(jié)果是從小到大排序的。

插入排序思路：

假設(shè)有個待排序數(shù)組（黑色數(shù)字），定義一個 i 下標(biāo)，一個 j 下標(biāo)，再定義一個記錄i下標(biāo)的值的ret。

首先，i 下標(biāo)從 1 位置開始，j 下標(biāo)在 i - 1位置開始，當(dāng) j 下標(biāo)的值比 ret 的值大，把 j 下標(biāo)的值給到 j+1 的位置。反之 把ret 的值給到 j+1的位置。以此往復(fù)。

值得注意的是，比如數(shù)組的最小的元素（上圖的是0）， j 會到達下標(biāo)為 -1 的位置，此時，循環(huán)里的  arr[j+1] = ret; 這句代碼就執(zhí)行不到了，意思就是數(shù)組最小元素 0 放不到下標(biāo)為 0 的位置。所以在外面 加上一句 arr[j+1] = ret; 代碼。這句代碼和 循環(huán)里的這句代碼重復(fù)了，就把 循環(huán)里的這句代碼注釋了。

 希爾排序（不穩(wěn)定）：

什么是希爾排序：

把待排序數(shù)據(jù)分成多個組，所有距離為的記錄分在同?組內(nèi)，并對每?組內(nèi)的記錄進行插入排序。然后，重復(fù)上述分組和排序的過程。當(dāng)?shù)竭_=1時，所有記錄在統(tǒng)?組內(nèi)排好序。

什么意思呢？

如圖：

先假定 gap的大小，這里初始的 gap 是5，讓 每個數(shù)據(jù)之間都相差 距離為 gap 的大小，如果后面的最遠(yuǎn)的數(shù)據(jù)相差比 gap小就 不相連，這樣就為一組了。下一個 組 從第二個數(shù)據(jù)開始，直到包含所有數(shù)據(jù)。分組就結(jié)束了。

然后，對其中的一趟的 每一組進行插入排序，再不斷縮小gap的大小，直到gap的大小為1，gap的大小為1就是一次完整的插入排序了。當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。

所有，可以說希爾排序是對插入排序的優(yōu)化。

一樣，我們假設(shè)有這樣一個數(shù)組，想要從小到大進行排序：

 int[] array = {4,9,5,8,6,2,10,7,3,1};

希爾排序代碼實現(xiàn)：

 public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while(gap > 0) {
            shell(arr,gap);
            gap /= 2;
        }
    }

    public static void shell(int[] arr,int gap) {
        for (int i = gap; i < arr.length; i++) {
            int ret = arr[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if(arr[j] > ret) {
                    arr[j+gap] = arr[j];
                }else {
                    //arr[j+1] = ret;
                    break;
                }
            }
            arr[j+gap] = ret;
        }
    }

希爾排序思路：

結(jié)合上圖，這是 gap 為 2 的時候的情況，與插入排序類似，結(jié)合代碼看，把紅色組別看成一組數(shù)據(jù)，先讓 下標(biāo) i 等于 gap的位置，j 在 i - gap 的位置，確保他們是在紅色組別位置進行插入排序，下一次，i 加加，到了綠色組別位置，再讓 j 在 i - gap 的位置，確保他們是在綠色組別位置進行插入排序?？梢钥闯觯麄兪窃诩t色和綠色組別交替進行插入排序的。

直到 gap 為 1 ，就可以看作一次普通的插入排序了。      

至于起始的 gap 選多大是無法給出正確答案的，希爾排序時間復(fù)雜度不好計算，因為 gap 的取值很多，導(dǎo)致很難去計算。

總結(jié)

到此這篇關(guān)于java插入排序和希爾排序?qū)崿F(xiàn)思路及代碼的文章就介紹到這了,更多相關(guān)java插入排序和希爾排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論