希尔排序的C语言实现（2）

代码 #include  < stdio.h > #include  < stdlib.h > void  ShellSort( int  a[], int  Index); void  PrintArray( const   char *  strMsg, int  array[], int  nLength); int  main( int  argc,  char   * argv[]){   int  data[ 13 ] = { 8 , 5 , 4 , 6 , 13 , 7 , 1 , 9 , 12 , 11 , 3 , 10 , 2 };  ShellSort(data, 13 );   // PrintArray("Shell Sort:",data,13);     system( " PAUSE " );       return   0 ;} /*  希尔排序的思路：       需要三层循环，       第一层循环用于控制步长的变化，步长每缩减一次就进行一轮排序；        第二层循环用于控制按照步长所分割成的各个集合；        第三层循环用于针对单个集合进行插入排序；    注：通过画图观察步长与小组个数的关系，可以知道，对于有13个元素的数组，       当步长为8时，可把数组分为8个小组，其中5组有2个元素,3组只有1个元素        当步长为7时，可把数组分为7个小组，其中1组有1个元素,6组有2个元素       当步长为6时，可把数组分为6个小组，其中1组有3个元素,5组有2个元素       当步长为5时，可把数组分为5个小组，其中3组有3个元素,2组有2个元素       当步长为4时，可把数组分为4个小组，其中1组有4个元素,3组有3个元素 */ void  ShellSort( int  a[], int  Index) {      int  i, j, k;     //  循环计数变量       int  Temp;        //  暂存变量       int  Change;      //  数据是否改变       int  DataStep;    //  集合分割的步长       int  Pointer;     //  进行处理的位置      DataStep  =  ( int ) Index  /   2 ;  //  初始集合间隔长度       while  (DataStep  !=   0 )  //  数列仍可进行分割     {     printf( " ========================\n " );     //  对各个集合进行处理    /*（在j自增至DataStep的2倍之前，j代表各小组的第二个元素的位置;        j增至DataStep的3倍之前,j代表各小组的第三个元素的位置;依次类推。        若j-DataStep<0说明j已经是本小组的第一个元素了。）*/         for  (j  =  DataStep; j  <  Index; j ++ ) {         Change  =   0 ;         Temp  =  a[j];  // 保存当前集合的待排序元素到临时变量              //（推算本元素的前一个元素的位置）      Pointer  =  j  -  DataStep;  // 计算当前集合已排序元素列表的最后一个元素的位置        k = 0 ;       //  进行集合内数值的插入排序（边比较边向后移位）         while  (Temp  <  a[Pointer]  &&  Pointer  >=   0   &&  Pointer  <=  Index) {        printf( " 当前交换元素：%d(a[%d])-%d(a[%d])\n " ,a[Pointer],Pointer,a[Pointer  +  DataStep],Pointer  +  DataStep);         // 将比待排序元素大的已排序元素后移         a[Pointer  +  DataStep]  =  a[Pointer];         PrintArray( " 本次交换结果:  " ,a,Index);         // 计算下一个要比较的已排序元素的位置          Pointer  =  Pointer  -  DataStep;         Change  =   1 ;        k ++ ;       }       printf( " 本集合步长为%d,交换次数为%d\n " ,DataStep,k);             //  （将待排序元素插入到最后的空位上）        a[Pointer  +  DataStep]  =  Temp;       if  (Change) {             //  打印目前排序结果         PrintArray( " 本轮排序结果:  " ,a,Index);       }         printf( " ------------------------\n " );    }       DataStep  =  DataStep  /   2 ;  //  计算下次分割的间隔长度      }   }  void  PrintArray( const   char *  strMsg, int  array[], int  nLength){      int  i;     printf( " %s " ,strMsg);      for (i = 0 ;i < nLength;i ++ )     {        printf( " %d  " ,array[i]);     }     printf( " \n " );}

 

转载于:https://www.cnblogs.com/feima-lxl/archive/2010/08/19/1803709.html

相关资源：C语言实现希尔排序算法