Java算法之希尔排序

举例：要排序的数组  int[] arr={7,9,8,4,5,1,6,3,2,0};

从小到大排列：

/*
希尔排序
*/
public class ShellSort {
	public static void main(String[] arrrgs) {
		int[] arr={7,9,8,4,5,1,6,3,2,0};
		int d=arr.length;
        while(true)
        {
            d=d/2;
            for(int x=0;x<d;x++)
            {
                for(int i=x+d;i<arr.length;i=i+d)
                {
                    int temp=arr[i];
                    int j;
                    for(j=i-d;j>=0&&arr[j]>temp;j=j-d)
                    {
                        arr[j+d]=arr[j];
                    }
                    arr[j+d]=temp;
                }
            }
            if(d==1)
            {
                break;
            }
        }
        for(int b=0;b<arr.length;b++){//输出
		    System.out.println(arr[b]);
        }
	}
}

运行结果：

0
1
2
3
4
5
6
7
8
9

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量

 =1(

 <

  …<d2<d1)，即将所有记录放在同一组中进行直接插入排序为止。