排序算法——希尔排序（两种实现）

之前写了快速排序和归并排序，虽然这两种排序算法问的最多，也具有一定的难度。希尔排序作为插入排序的一种，里面有着插入排序的影子。我会讲解一下希尔排序的两种实现方式。

对于希尔排序，重点在于增量。什么是增量，即希尔排序会分组进行操作，而分组的依据就是通过增量来执行的。那么增量又是什么呢？我画图来讲解一下吧~

知道了增量那么就很简单了。就是根据组内的值进行比较即可。那么希尔排序有两种方法实现：

①交换法（速度慢，不建议用）

②移位法（利用插入排序的思想进行交换法的优化，速度快，建议希尔排序用这个方法实现）

①交换法代码实现：

public static void shellSort(int arr[]){
          
   
		//交换变量
		int temp = 0;
		//第一个循环设置增量
		for(int step = arr.length / 2; step > 0; step /= 2){
          
   
			//第二个循环找到分组后面的数据
			for(int i = step; i < arr.length; i++){
          
   
				//第三个循环找到分组前面的数据
				for(int j = i - step; j >= 0; j -= step){
          
   
					//判断前面的值是否大于后面的值
					if(arr[j] > arr[j + step]){
          
   
						//交换
						temp = arr[j];
						arr[j] = arr[j + step];
						arr[j + step] = temp;
					}
				}
			}
		}
	}

虽然这样的写法比较容易理解，但是效率并不高，总所周知冒泡排序是排序算法中效率很慢的，这是因为它每次都进行了数值的交换，这样会耗费大量的时间，那么这样的写法也是同样的道理。那么我们再来实现移位法。

②移位法代码实现

public static void shellSort(int arr[]){
          
   
		//和交换法一样，都需要增量去分组
		for(int step = arr.length / 2; step > 0; step /= 2){
          
   
			//同样我们得找到分组后面的数据
			for(int i = step; i < arr.length; i++){
          
   
				//设置指针指向i去操作分组前的数据
				int j = i;
				//存储当前的数据，后面数据会发生变化
				temp = arr[j];
				if(arr[j] < arr[j - temp]){
          
   
					//要清楚j存储的是分组后面的数据
					while(j - step >= 0 && temp < arr[j - step]){
          
   
						//将前面的值移位到j上，此时j与j-step都为arr[j - step]的值
						arr[j] = arr[j - step];
						//将指针在组内往前移动，继续寻找
						j -= step;
					}
					//当循环结束的时候，就是找到了位置，那么需要将temp赋值给分组前面的值
					arr[j] = temp;
				}
			}
		}
	}

这样移位法就完成了，这样借助了交换法和插入排序的思想，进行代码的优化，这样的效率就会快很多了，有兴趣的可以拿这两个代码去测试一下。