java高等排序之希爾排序

java高等排序之希爾排序。本站提示廣大學習愛好者：（java高等排序之希爾排序）文章只能為提供參考，不一定能成為您想要的結果。以下是java高等排序之希爾排序正文

希爾排序關於多達幾千個數據項的，中等年夜小范圍的數組排序表示優越，希爾排序不像疾速排序和其它時光龐雜度為O（n*logn)的排序算法那末快，是以，對異常年夜的文件排序，它不是最優選擇，然則希爾排序比選擇排序和拔出排序這類時光龐雜度為O(n²)的排序要快的多，而且它異常輕易完成，代碼冗長

　　希爾排序也是拔出排序的一種，在拔出排序中，假如最小的數在最初面，則復制的次數太多，而希爾處理了這個成績，它也是n-增量排序，它的思惟是經由過程加年夜拔出排序中元素的距離，並在這些有距離的元素中停止拔出排序，當這些數據項排過一趟序後，希爾排序算法減小數據項的距離再停止排序，依此停止下去。停止這些排序時數據項之間的距離被稱為增量，而且習氣上用字母h來表現。

　　關於某個立時要停止希爾排序的數組，開端的距離應當更年夜，然後距離不段減小，直到距離變成1.

距離序列：

　　距離序列中的數字本質平日被以為很主要-除1以外它們沒有條約數，這個束縛前提使每趟排序更有能夠堅持前一趟排序已排好的後果，關於分歧的距離序列，有一個相對的前提，就是逐步減小的距離最初必定要等於1.是以最初一趟是一次通俗的拔出排序。

　　上面列出的例子是h=h*3+1的紀律得出的：

package com.jll.sort;
public class ShellSort {
  int[] arr;
  int size;
  
  public ShellSort() {
    super();
  }
  
  public ShellSort(int size) {
    this.size = size;
    arr = new int[size];
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    ShellSort ss = new ShellSort(10);
    for(int i=0;i<10;i++){
      ss.arr[i] = (int) ((Math.random()*100)+1);
      System.out.print(ss.arr[i]+" ");
    }
    ss.shellSort();
    System.out.println();
    System.out.println("after sort:");
    for(int i=0;i<10;i++){
      System.out.print(ss.arr[i]+" ");
    }
    
  }
  
  public void shellSort(){
    int h = 1;
    while(h<=size/3){
      h = h*3+1;
    }
    for(;h>0;h=(h-1)/3){
      for(int i=h;i<size;i++){
        int temp = arr[i];
        int j = i;
          while(j>h-1&&arr[j-h]>temp){
            arr[j]=arr[j-h];
            j-=h;
          }
          arr[j]=temp;
        }
      }
    }
  }