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

时间：2010-08-19 来源：LeeXiaoLiang

代码 #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;
}

/* 希尔排序的思路：
       需要三层循环，
       第一层循环用于控制步长的变化，步长每缩减一次就进行一轮排序；
       第二层循环用于控制按照步长所分割成的各个集合；
       第三层循环用于针对单个集合进行插入排序；
*/
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");
    // 对各个集合进行处理
    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");
}