希尔排序（Java语言实现）

希尔排序：
在简单插入排序经过改进的更高效版本，也称缩小增量排序。
算法基本思想：
把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减小，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法终止。
希尔排序有两种方法：交换法(效率不高) 和移位法。
算法图解：


算法实现：
交换法：

//该算法是希尔排序中的交换法(效率不高)publicstaticvoidshellSort(int[] arr){int temp=0;int count=0;for(int stepSize= arr.length/2; stepSize>0; stepSize/=2){for(int i= stepSize; i< arr.length; i++){//遍历各组中所有的元素(共stepSize组)，步长为stepSizefor(int j= i- stepSize; j>=0; j-= stepSize){//如果当前元素大于加上步长后的那个元素，说明交换if(arr[j]> arr[j+ stepSize]){                         temp= arr[j];                         arr[j]= arr[j+ stepSize];                         arr[j+ stepSize]= temp;}}}System.out.println("希尔排序第"+(++count)+"轮"+Arrays.toString(arr));}System.out.println("排序的结果为:"+Arrays.toString(arr));}

这里的第三层循环 j -= stepSize，到第二轮stepSize = 2时，当时有点不理解，自己在纸上写了排序全过程：

它可以两组进行交叉排序，且保证有序性。

移位法：

//对交换式的希尔排序进行优化--->移位法publicstaticvoidshellSortPlus(int[] arr){//增量stepSize，并逐步缩小增量for(int stepSize= arr.length/2; stepSize>0; stepSize/=2){//从第stepSize个元素，逐个对其所在组进行直接插入排序for(int i= stepSize; i< arr.length; i++){int j= i;int temp= arr[j];if(arr[j]< arr[j-stepSize]){while(j- stepSize>=0&& temp< arr[j-stepSize]){//移动                         arr[j]= arr[j-stepSize];                         j-= stepSize;}//当退出while循环时就给temp找到插入的位置                     arr[j]= temp;}}System.out.println(Arrays.toString(arr));}System.out.println("希尔排序的结果为: "+Arrays.toString(arr));}

这个移位法算法的时间效率比交换法算法的时间效率高好多。