希尔排序之Java实现

￡神魔★判官ぃ 2022-06-16 06:12 128阅读 0赞

希尔排序思想：

希尔排序其实就是将一个数组分段进行插入排序，最后再将分段序列组合在一起进行大的插入排序。

也即：希尔排序是首先将数组分成若干子数组(一般子数组的个数是n/2或者n/m，n是数组长度，m是分隔间距)，然后每个子数组进行插入排序；再缩减增量（一般缩减增量表达式是 k/2，k是上一次执行插入排序结束之后的子数组的长度），进行插入排序；直到子数组足够小，那么再对总的数组进行插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                                 1B

2A                                  2B

3A                                  3B

4A                                 4B

5A                                   5B

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4    49   38   65   97   26

1A          1B          1C         1D          1E

2A           2B         2C          2D          2E

第三次 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A 1B  1C   1D  1E   1F   1G   1H   1I    1J

第四次 gap = 1 / 2 = 0 排序完成得到数组：

4   13   26   27   38    49   49   55   65   97

代码实现是：

public static void shellSort(int [] arr){
    		int i,j,k,gap = arr.length;
    		//第一个循环决定进行比较的间隔
    		for(gap = arr.length / 2 ; gap > 0 ; gap /=2){
    			//第二个循环根据间隔，将整个数组分成若干子数组
    			for(i = 0 ; i < gap ; i++){
    				//下面两个循环就是子数组内部的插入排序算法
    				for(j = i + gap ; j < arr.length ; j += gap){
    					if(arr[j] < arr[j-gap]){
    						int temp = arr[j];
    						for(k = j - gap ; k >= 0 && arr[k] > temp; k -= gap){
    							arr[k + gap] = arr[k];
    						}
    						arr[k + gap] = temp;
    					}
    				}
    			}
    		}
    	}

测试代码：

public static void main(String[] args) {
    		int [] arr = {49, 38, 65, 97, 26, 13, 27, 49, 55, 4};
    		shellSort(arr);
    		for(int i : arr){
    			System.out.println(i);
    		}
    	}

参考资料：http://blog.csdn.net/morewindows/article/details/6668714