java高級排序之希爾排序

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

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

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

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

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

間隔序列：

　　間隔序列中的數字素質通常被認為很重要-除了1之外它們沒有公約數，這個約束條件使每趟排序更有可能保持前一趟排序已排好的效果，對于不同的間隔序列，有一個絕對的條件，就是逐漸減小的間隔最后一定要等于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;
        }
      }
    }
  }

您可能感興趣的文章:

String類型傳遞是值傳遞,char[]類型傳遞是引用傳遞的實現
下面小編就為大家?guī)硪黄猄tring類型傳遞是值傳遞,char[]類型傳遞是引用傳遞的實現。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看不
2016-09-09
MQ的消息模型及在工作上應用場景
這篇文章主要介紹了MQ的消息模型及在工作上應用場景，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-05-05
Java實現Kafka生產者和消費者的示例
這篇文章主要介紹了Java實現Kafka生產者和消費者的示例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2021-02-02
在spring中使用自定義注解注冊監(jiān)聽器的方法
本篇文章主要介紹了在spring中使用自定義注解注冊監(jiān)聽器的方法，本文就是在分析監(jiān)聽器回調原理的基礎上，在spring環(huán)境中使用自定義的注解實現一個監(jiān)聽器。小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2018-01-01
Java中Scanner類與BufferReader類的不同點(非常詳細)
這篇文章主要介紹了Java中Scanner類與BufferReader類的不同點(非常詳細)的相關資料,需要的朋友可以參考下
2016-08-08
springboot集成springsecurity 使用OAUTH2做權限管理的教程
這篇文章主要介紹了springboot集成springsecurity 使用OAUTH2做權限管理的教程，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
SpringBoot配置數據庫密碼加密的方法
由于系統安全的考慮,配置文件中不能出現明文密碼的問題,本文就給大家詳細介紹下springboot配置數據庫密碼加密的方法,下面話不多說了,來一起看看詳細的介紹吧,需要的朋友可以參考下
2023-08-08
淺談為什么重寫equals()就要重寫hashCode()
困擾我很久的問題,一直不明白為什么重寫equals()方法的時候要重寫hashCode()方法，這次總算弄明白了，作此分享，感興趣的可以了解一下
2021-10-10
SpringCloud超詳細講解微服務網關Gateway
這篇文章主要介紹了SpringCloud Gateway微服務網關，負載均衡，熔斷和限流，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2022-07-07
Spring?Cache抽象-使用SpEL表達式解析
這篇文章主要介紹了Spring?Cache抽象-使用SpEL表達式解析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2021-12-12