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

例如数组：arr={2,5,6,7,8,1}使用插入排序时，将1移到最前面的位置，需要使前面所有的位置都发生移动，因此对于这种情况，插入排序的效率会大大降低。
什么是插入排序？

针对上述情况，我们可以利用希尔排序的方式进行解决。
希尔排序本身就是插入排序，它是一种更高效的版本，也称为缩小增量排序。

1. 先对数组进行一定增量的分组；
2. 将各个分组进行插入排序算法进行排序；
3. 随着分组增量的减少，当减至1时，分为一组，排序结束。

1. 利用交换进行组内排序

	public static void shellSort(int []arr){
		//第1个for设置步长
		for(int gap = arr.length / 2; gap > 0; gap /= 2){
			//第2个for根据步长进行分组
			for(int i = gap;i < arr.length;i++){
				//第3个for对每一个组进行排序
				for(int j = i - gap;j >= 0;j -= gap){
					//交换
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
	}

2. 利用插入进行组内排序

	for(int gap = arr.length / 2;gap > 0;gap /= 2){
		for(int i = gap; i < arr.length;i++){
			int j = i;
			int temp = arr[j];
			if(arr[j] < arr[j - gap]){
				while(j - gap >= 0 && temp < arr[j - gap]){
					arr[j] = arr[j - gap];
					j -= gap;
				}
				arr[j] = temp;
			}
		}
	}

• 两种方式在思想上是不变的，都是分组，再对分组后的每一次进行排序，只是具体采用的排序算法不同，一个是交换，一个是插入排序。