java希爾排序的實例詳解

這篇文章主要介紹了java資料結構與演算法之希爾排序,結合實例形式分析了希爾排序的概念、原理、實現方法與相關注意事項,需要的朋友可以參考下

本文實例講述了java資料結構與演算法之希爾排序。分享給大家供大家參考，具體如下：

這裡要介紹的是希爾排序（縮小增量排序法）。

希爾排序：透過比較相距一定間隔的元素來運作；各趟比較所用的距離（增量）隨著演算法的進行而減小，直到只比較相鄰元素的最後一趟排序為止。是插入排序的一種，是針對直接插入排序演算法的改進。

演算法想法：先將要排序的序列按某個增量d分成若干個子序列，對每個子序列中全部元素分別進行直接插入排序，然後再用一個較小的增量對它進行分組，在每組中再排序。當增量減到1時，整個要排序的數被分成一組，排序完成。注意：增量的值－一般的初次取序列的一半為增量，以後每次減半，直到增量為1。

演算法實作程式碼如下：

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //设置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步长
      for (int i = average; i < array.length; i++) { //子序列进行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

#演算法分析：該演算法是依照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本上有序了，步長很小，插入排序對於有序的序列效率很高。所以，希爾排序的時間複雜度會比O(n^2)好一些，為O(n^1.5)，排序效率比插入排序高很多。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。 希爾排序沒有快速排序演算法快O(N*(logN))，因此對中等大小規模的資料排序比較適用，對規模非常大的資料排序不是最優選擇 #。但是比O(N^2)複雜度的演算法快得多。而且希爾排序非常容易實現，演算法程式碼短而簡單。 此外，希爾演算法在最壞的情況下和平均情況下執行效率相差不是很多，同時快速排序在最壞的情況下執行的效率會非常差。

【相關推薦】

1. 特別推薦#：「php程式設計師工具箱」V0.1版本下載

2. Java免費影片教學

3. YMP線上手冊

#

以上是java希爾排序的實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！