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

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

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

有关排序的介绍，看上一个笔记：《常见算法和数据结构》元素排序(1)——简单排序（附动画）

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

希尔排序思想

希尔的思想也很简单就是一个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)