快捷導(dǎo)航

java插入排序和希爾排序?qū)崿F(xiàn)思路及代碼

更新時(shí)間：2025年03月10日 08:29:12 作者：Excuse_lighttime

這篇文章主要介紹了插入排序和希爾排序兩種排序算法,文章通過代碼示例和圖解詳細(xì)介紹了這兩種排序算法的實(shí)現(xiàn)過程和原理,需要的朋友可以參考下

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

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

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

插入排序代碼實(shí)現(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;
        }
    }

代碼運(yùn)行結(jié)果：

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

插入排序思路：

假設(shè)有個(gè)待排序數(shù)組（黑色數(shù)字），定義一個(gè) i 下標(biāo)，一個(gè) j 下標(biāo)，再定義一個(gè)記錄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 會(huì)到達(dá)下標(biāo)為 -1 的位置，此時(shí)，循環(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ù)分成多個(gè)組，所有距離為的記錄分在同?組內(nèi)，并對每?組內(nèi)的記錄進(jìn)行插入排序。然后，重復(fù)上述分組和排序的過程。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)?組內(nèi)排好序。

什么意思呢？

如圖：

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

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

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

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

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

希爾排序代碼實(shí)現(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 的時(shí)候的情況，與插入排序類似，結(jié)合代碼看，把紅色組別看成一組數(shù)據(jù)，先讓下標(biāo) i 等于 gap的位置，j 在 i - gap 的位置，確保他們是在紅色組別位置進(jìn)行插入排序，下一次，i 加加，到了綠色組別位置，再讓 j 在 i - gap 的位置，確保他們是在綠色組別位置進(jìn)行插入排序。可以看出，他們是在紅色和綠色組別交替進(jìn)行插入排序的。

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

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