排序法：希尔排序

希尔排序 ：

（缩小增量排序）

 排序原理：设置一个增量n，将所有下标为增量倍数的值放入到一个组中，对该组进行排序，然后重复这个方法，取增量m (m < n ，后面所取的增量应该递减)，查找到增量m倍数的值进行排序。

希尔排序属于插入排序，是将整个有序序列分割成若干小的子序列分别进行插入排序。

 

（注：增量应该小于该数组的长度，一般取 length / 2 的整数值，有关增量的取值， 这里不进行讨论）

 

 

 

public class ShellSort
{
    //shell sort: 按增量取值分组排序。
    public void shellSortFun(int[] arrs)
    {
        if (arrs != null && arrs.length != 0)
        {
            int increment = arrs.length / 2;
            
            boolean flag = true;
            while (flag)
            {
                for (int i = 0 ; i < increment ; i ++)
                {
                    for (int j = 0 ; j < arrs.length; j++)
                    {
                        if ((j + increment) < arrs.length)
                        {
                           if (arrs[j] - arrs[j + increment] > 0)
                           {
                               int tmp = 0;
                               tmp = arrs[j];
                               arrs[j] = arrs[j + increment];
                               arrs[j + increment] = tmp;
                           }
                        }
                    }
                }
                
                increment = increment / 2;
                if (increment == 1)
                {
                    break;
                }
            }
            
            for (int i = 1 ; i < arrs.length; i++)
            {
                int tmp = arrs[i];
                int index = i;
                while (index > 0 && (tmp < arrs[index - 1]))
                {
                    arrs[index] = arrs[index - 1];  
                    index --;  
                }
                arrs[index] = tmp;  
            }
            
            for (int arr : arrs)
            {
                System.out.println(arr);
            }
        }
    }
    
    
    public static void main(String[] args)
    {
        ShellSort ss = new ShellSort();
        Random rd = new Random();
        int[] arrs = new int[100];
        for (int i = 0 ; i < 100; i++)
        {
            arrs[i] = rd.nextInt();
        }
       
//        int[] arrs = new int[]{3,2,1,5,6,9,8,7,-2,10};//49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1
        ss.shellSortFun(arrs);
    }
    
}

 

下面这个动画演示能清晰的看出希尔排序是怎样运行的 ：

【动画演示】