快捷導航

java高級排序之希爾排序

更新時間：2015年04月08日 22:46:11 投稿：mdxy-dxy

這篇文章主要介紹了java高級排序之希爾排序 ,需要的朋友可以參考下

希爾排序?qū)τ诙噙_幾千個數(shù)據(jù)項的，中等大小規(guī)模的數(shù)組排序表現(xiàn)良好，希爾排序不像快速排序和其它時間復雜度為O（n*logn)的排序算法那么快，因此，對非常大的文件排序，它不是最優(yōu)選擇，但是希爾排序比選擇排序和插入排序這種時間復雜度為O(n²)的排序要快的多，并且它非常容易實現(xiàn)，代碼簡短

　　希爾排序也是插入排序的一種，在插入排序中，如果最小的數(shù)在最后面，則復制的次數(shù)太多，而希爾解決了這個問題，它也是n-增量排序，它的思想是通過加大插入排序中元素的間隔，并在這些有間隔的元素中進行插入排序，當這些數(shù)據(jù)項排過一趟序后，希爾排序算法減小數(shù)據(jù)項的間隔再進行排序，依此進行下去。進行這些排序時數(shù)據(jù)項之間的間隔被稱為增量，并且習慣上用字母h來表示。

　　對于某個馬上要進行希爾排序的數(shù)組，開始的間隔應該更大，然后間隔不段減小，直到間隔變?yōu)?.

間隔序列：

　　間隔序列中的數(shù)字素質(zhì)通常被認為很重要-除了1之外它們沒有公約數(shù)，這個約束條件使每趟排序更有可能保持前一趟排序已排好的效果，對于不同的間隔序列，有一個絕對的條件，就是逐漸減小的間隔最后一定要等于1.因此最后一趟是一次普通的插入排序。

　　下面列出的例子是h=h*3+1的規(guī)律得出的：

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;
        }
      }
    }
  }

您可能感興趣的文章: