package sort;/**希尔排序的原理:根据需求，如果你想要结果从小到大排列，它会首先将数组进行分组，然后将较大值移到前面，较小值  * 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强  * 版的插入排序  * 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列  * 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较  * 此例子是按照从小到到排列，所以小的会排在前面，第一次排序后数组为5, 1, 3, 4, 2, 8，9 * 第一次后increment的值变为3/2=1,此时对数组进行插入排序，  */  public class ShellSort {      public static void shellSort(int[] list) {          //把数组分成两组        for (int increment = list.length / 2; increment > 0; increment /= 2) {            //从第二组的第一个数的下标开始        	for (int i = increment; i < list.length; i++) {          		//此为第二组第一个下标处的值               int  temp = list[i];                 int j =0;                               for ( j = i; j >= increment; j -= increment) {                  	//j-increment 为第一组对应下标的值，如果它大，就被交换至第二组                	//相应下标处                    if(temp < list[j - increment]){                          list[j] = list[j - increment];                      }else{                          break;                      }                  }                   //此时如果if里的成立，则j值已经为j-increment，即第一组下标处的值为第二组相应下标值                //如果if里的不成立 ，j不变，还是原来的值                list[j] = temp;              }          }      }        public static void main(String[] args){		int[] list ={5 , 2 , 8,  9 ,1,3,4,};		shellSort(list);		for(int i =0;i<list.length;i++){			System.out.print(list[i]+" ");		}	}  }