Java 插入排序之希尔排序的实例

/*希尔排序(Shell Sort)是插入排序的一种。其基本思想是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1    * 个组，所有距离为d1的倍数的记录放在同一个组中，在各个组中进行插入排序；然后，取第二个增量d2<d1，重复上述的分组和排序，    * 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止。    * new int[]{8,5,1,7,9,4,6}，开始分割集合的间隔长度为3的情况，[[6][3][0]比较排序后，[4]和[1]比较排序后，[5]和[2]比较排序后，    * 分割集合的间隔长度为1，这时[1]和[0]比较排序后，[2][1][0]....,和直接插入排序一样了。*/   public static void shellSort(int[] intArray) {      System.out.print("将要排序的数组为:    ");      for(int k=0;k<intArray.length;k++)         System.out.print(" "+intArray[k]+" ");       System.out.println();          int arrayLength=intArray.length;     int j,k;//循环变量     int temp;//暂存变量     boolean isChange;//数据是否改变     int dataLength;//分割集合的间隔长度     int pointer;//进行处理的位置     dataLength=arrayLength/2;//初始集合间隔长度     while(dataLength!=0){//数列仍可进行分割       //对各个集合进行处理       for(j=dataLength;j<arrayLength;j++){         isChange=false;         temp=intArray[j];//暂存，待交换值时用         pointer=j-dataLength;//计算进行处理的位置         //进行集合内数值的比较与交换值         while(temp<intArray[pointer]&&pointer>=0&&pointer<arrayLength){           intArray[pointer+dataLength]=intArray[pointer];           //计算下一个欲进行处理的位置           pointer=pointer-dataLength;           isChange=true;           System.out.print("every changing result: ");           for(k=0;k<arrayLength;k++)             System.out.print(" "+intArray[k]+" ");           System.out.println();           if(pointer<0||pointer>arrayLength)             break;         }         //与最后的数值交换         intArray[pointer+dataLength]=temp;         if(isChange){           System.out.print("Current sorting result: ");           for(k=0;k<arrayLength;k++)             System.out.print(" "+intArray[k]+" ");           System.out.println();         }       }       System.out.print("指定分割集合的间隔长度为"+dataLength+"，对各个集合进行处理后，Current sorting result: ");       for(k=0;k<arrayLength;k++)         System.out.print(" "+intArray[k]+" ");       System.out.println();       dataLength=dataLength/2;//计算下次分割的间隔长度     }   } 

将要排序的数组为:     8 5 1 7 9 4 6  every changing result: 8 5 1 8 9 4 6  Current sorting result: 7 5 1 8 9 4 6  every changing result: 7 5 1 8 9 4 8  every changing result: 7 5 1 7 9 4 8  Current sorting result: 6 5 1 7 9 4 8  指定分割集合的间隔长度为3，对各个集合进行处理后，Current sorting result: 6 5 1 7 9 4 8  every changing result: 6 6 1 7 9 4 8  Current sorting result: 5 6 1 7 9 4 8  every changing result: 5 6 6 7 9 4 8  every changing result: 5 5 6 7 9 4 8  Current sorting result: 1 5 6 7 9 4 8  every changing result: 1 5 6 7 9 9 8  every changing result: 1 5 6 7 7 9 8  every changing result: 1 5 6 6 7 9 8  every changing result: 1 5 5 6 7 9 8  Current sorting result: 1 4 5 6 7 9 8  every changing result: 1 4 5 6 7 9 9  Current sorting result: 1 4 5 6 7 8 9  指定分割集合的间隔长度为1，对各个集合进行处理后，Current sorting result: 1 4 5 6 7 8 9