欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java 算法之希尔排序详解及实现代码

程序员文章站 2024-03-05 09:26:06
java 算法之希尔排序 一、思想 希尔排序:使数组中任意间隔为h的元素都是有序的。在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有...

java 算法之希尔排序

一、思想

希尔排序:使数组中任意间隔为h的元素都是有序的。在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对任意以1结尾的h序列,我们都能够将数据排序; 

 二、概念

h有序数组:任意间隔为h的元素都是有序的数组; 

三、高效原因

对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一段;

  希尔排序更高效的原因:它权衡了子数组的规模和有序性,在排序之初,各个子数组都很短;在排序之后子数组都是部分有序的,这两种情况很适合插入排序;  

四、代码

/** 
 * 希尔排序 
 *  
 * @author pengcx 
 *  
 */  
public class shell extends sort {  
  public static void main(string[] args) {  
    string[] a = { "d", "a", "w", "b", "q" };  
    shell.sort(a);  
    show(a);  
  }  
  
  /** 
  * 排序数组a 
  *  
  * @param a 
  *      排序的数组a 
  */  
  protected static void sort(comparable[] a) {  
    int n = a.length;  
    int h = 1;  
    while (h < n / 3) {  
      h = 3 * h + 1;  
    }  
  
    while (h >= 1) {  
      for (int i = 0; i < n; i++) {  
        for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {  
          exch(a, j, j - h);  
        }  
      }  
      h = h / 3;  
    }  
  }  
}  

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!