Java排序算法之——希爾排序

Enlightenment 發(fā)布于2019-08-14 12:21 / 1506人閱讀

摘要：算法簡(jiǎn)述希爾排序也叫作排序或縮小增量排序，據(jù)說(shuō)是一個(gè)叫的人發(fā)明出來(lái)的，顧取名排序。這種排序是基于插入排序思想的，也比較適用于數(shù)據(jù)量大時(shí)。

算法簡(jiǎn)述

希爾排序也叫作shell排序或縮小增量排序，據(jù)說(shuō)是一個(gè)叫D.L.Shell的人發(fā)明出來(lái)的，顧取名shell排序。這種排序是基于插入排序思想的，也比較適用于數(shù)據(jù)量大時(shí)。

我剛開(kāi)始看到時(shí)候?qū)τ诓迦肱判蛞彩前肫孔哟祝苯訉?dǎo)致我看不懂了，抓狂，so...我就去默默的補(bǔ)習(xí)一下插入排序嘍。

插入排序簡(jiǎn)介

插入排序的核心思想是比較和插入，就是從第二個(gè)數(shù)開(kāi)始，依次插入到前面合適的位置。排序步驟如下：

1. 首先對(duì)數(shù)組的前兩個(gè)數(shù)據(jù)進(jìn)行從小到大的排序
2. 接著將第3個(gè)數(shù)據(jù)與排序好的兩個(gè)數(shù)據(jù)進(jìn)行比較，插入合適的位置
3. 然后，將第4個(gè)數(shù)據(jù)插入已經(jīng)排好的前3個(gè)數(shù)據(jù)中
4. 不斷重復(fù)上述的過(guò)程，完成排序

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

private void insertSort(int[] a)
    {
        int i,j,t,h;
        for(i =1;i=0&&t
簡(jiǎn)單的介紹了一下插入排序，下面就講一下這個(gè)希爾排序。
排序步驟
1.將有n個(gè)元素的數(shù)組分為n/2個(gè)數(shù)字序列，第1個(gè)數(shù)據(jù)和第n/2+1個(gè)數(shù)據(jù)為一對(duì)。。。
2.一次循環(huán)使每一個(gè)序列對(duì)排好順序（對(duì)每個(gè)序列使用插入排序算法，實(shí)質(zhì)是一種分組插入）
3.然后，再變?yōu)閚/4個(gè)序列，再次排序
4.不斷重復(fù)上述過(guò)程，隨著序列減少最后變?yōu)橐粋€(gè)，也就完成了整個(gè)排序。

實(shí)例講解
比如對(duì){12,31,11,20,17，30}進(jìn)行希爾排序：
1. 第一次排序，首先將數(shù)組分為6/2=3個(gè)數(shù)字序列，第一個(gè)數(shù)據(jù)12和第四個(gè)數(shù)據(jù)20為一對(duì)，第二個(gè)數(shù)據(jù)和第五個(gè)數(shù)據(jù)為一對(duì)，第三個(gè)數(shù)據(jù)和第六個(gè)數(shù)據(jù)為一對(duì)，每一對(duì)進(jìn)行排序后數(shù)據(jù)為：12,17,11,20,31,30
2. 第二次排序，將數(shù)組劃分為6/4=1（這里取整），此時(shí)逐個(gè)對(duì)數(shù)據(jù)比較，按照插入排序算法進(jìn)行排序，排序后的數(shù)據(jù)為：11,12,17,20,30,31

代碼片段
private void shellSort(int[] a)
    {
        int i,j,h;
        int r,temp;
        int x = 0;
        for(r = a.length/2;r>=1;r/=2)
        {
            for(i = r;i=0&&temp
至此希爾排序就完成了，時(shí)間復(fù)雜度為O(nlog2n).