排序算法-希尔排序（Java）

希尔排序

希尔排序也是一种插入排序，是插入排序的更高效率的版本，也称为缩小增量排序

希尔排序的思想：

1. 把记录按照下标的一定增量分组
2. 对每组使用直接插入排序算法排序
3. 随着增量逐渐减少，每组包含的关键词越来越多
4. 当增量减至1时，整个恰好分成一组，算法终止，排序完成
   希尔排序示意图：
   
   最后直接进行微调即可，避免了像简单插入排序那样，当需要插入的数较小时，后移的次数明显增多，从而对效率有不好的影响

接下来列举两种实现方式：

1. 替换法
2. 移位法

	public static void shellSort(int [] arr){
		int temp = 0;//临时变量
		//gap表示步长，实现分组递减
		for(int gap = arr.length / 2;gap > 0; gap /= 2){
			for(int i = gap;i < arr.length;i++){//从步长开始依次递增
				//从头开始依次循环往回进行循环比较，使同一组内的数据保持按照顺序递增
				for(int j = i - gap;j >= 0;j -= gap){
					if(arr[j] > arr[j + gap]){
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp; 
					}
				}
			}
		}
	}
	

	public static void shellSort(int [] arr){
		for(int gap = arr.length / 2;gap > 0;gap /= 2){
			for(int i = gap;i < arr.length;i++){//和上面原理一样
				int j = i;
				int temp = arr[i];//临时变量
				if(arr[j] < arr[j -gap]){//判断大小是否需要移位操作
					while(j - gap >= 0 && arr[j] < arr[j - gap]){//如果前面比后面元素大，则进行移位操作
						arr[j] = arr[j - gap];
						j -= gap;
					}
					//当while循环结束后需要将临时变量元素插入到相对位置上
					//因为上面的移位只是将 大的元素放到了后面，而小的元素还没换到前面
					//这里就是将小元素放到前面，为什么给arr[j]赋值，因为上面循环最后执行了 j = j-gap
					//已经指向了前面位置
					arr[j] = temp;
				}
			}
		}
	}