元素排序(2)——希尔排序

2016-05-10   |     |     |  

本系列文章主要介绍常用的算法和数据结构的知识,记录的是《Algorithms I/II》课程的内容,采用的是“算法(第4版)”这本红宝书作为学习教材的,语言是java。这本书的名气我不用多说吧?豆瓣评分9.4,我自己也认为是极好的学习算法的书籍。

通过这系列文章,可以加深对数据结构和基本算法的理解(个人认为比学校讲的清晰多了),并加深对java的理解。

希尔排序是这是本课程中出现的第一个非平凡的排序算法。

希尔排序

希尔的思想也很简单就是一个h-sort插入算法——每相邻h个元素进行插入排序

为什么是插入排序?

  • 如果h比较大,那么子数组会很小,用插入效率高
  • 如果h很小,这时候数组基本有序,插入效率高

h的确定方法

一般常用的是 : h=3h+1——兼顾奇偶

希尔排序的特点

简单的想法却导致巨大的性能收益

  • 在实际使用中,对于不是特别大的数组,排序速度快。
  • 代码量小(可用于嵌入式中)
  • 硬件类算法原型
  • 通过找更好的递增数列可以有更好的性能提升(这是一个新的课题)

代码

public class Shell{
    public static sort(Comparable[] a)
    {
        int N = a.length();
        int h = 1;
        while(h < N/3)   //找比n小的最大h
            h = 3*h+1;
        do{
            for(i = h;i < N; i++)
            {
                for(j = i;j >= h && less(a[j],a[j-h]);j -= h)  
                exch(a,a[j],a[j-h]);
            }
            h = h/3;  //由于是取整操作所以h/3 == (h-1)/3
        }while(h > 1)
    }
}

注意: 这里的循环

    for(i = h;i < N; i++) 
      for(j = i;j >= h && less(a[j],a[j-h]);j -= h)

是用的i从前往后,j从后往前。j也可以用从前往后

    for(i = 0;i < N-h; i++) 
      for(j = i;j + h < N && less(a[j+h],a[j]);j += h)