欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-12-12 08:57:40
java 插入排序之希尔排序的实例 java代码  /*希尔排序(shell sort)是插入排序的一种。其基本思想是:先取定一个小于n的整数d1作为...

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

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;//计算下次分割的间隔长度 
    } 
  } 

 运行后的结果为:

java代码 

将要排序的数组为:     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 

 当分割的间隔为1时,变成了直接插入排序。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

上一篇:

下一篇: