java實現(xiàn)希爾排序完整代碼

• 排序是將一串?dāng)?shù)據(jù)按照其某個或者某些關(guān)鍵字的大小進行遞增或遞減排列的操作我，通常指的排序是升序，排序方式是原地排序
• 下面介紹下希爾排序

希爾排序

• 原理：
  • 指定一個值gap，將待排序區(qū)間分成gap個組，每個組相鄰元素的下標(biāo)差值是gap。將每個組元素進行排序
  • 減小gap的值，重復(fù)進行排序直到gap等于1
  • 當(dāng)gap等于1的時候，數(shù)組變成有序數(shù)組
• 實質(zhì)：
  • 希爾排序是對直接插入排序的優(yōu)化
  • 當(dāng)gap>1時都是進行序排序，當(dāng)gap=1時，數(shù)組已接近有序
• 希爾排序是一個不穩(wěn)定的排序

實現(xiàn)方式

    public void shellSort(int[] array) {
            int gap = array.length;
            while(gap > 1) {
                    insertSortGap(array, gap);
                    //gap的縮小方式?jīng)Q定了性能提升的程度
                    gap = gap / 3 + 1;
            }
            insertSortGap(array, 1);
    }

    private void insertSortGap(int[] array, int gap) {
            for(int i = 0; i < array.length; i++) {
                    int tmp = array[i];
                    int j = i - gap;
                    for(;j > 0 && array[j] > tmp; j -= gap) {
                            array[j + gap] = array[j];
                    }
                    array[j + gap] = tmp;
            }
    }

性能分析

• 時間復(fù)雜度
  • 最好情況：數(shù)組有序時時間復(fù)雜度是O(N)
  • 最快情況：時間復(fù)雜度是O(N^2)，很難構(gòu)造出實例
  • 平均情況：時間復(fù)雜度是O(N^1.3)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定