C/C++实现希尔排序（两种方式）

介绍

希尔排序又称 “缩小增量排序”，它也是一种插入类排序的方法。

希尔排序原理： 希尔排序属于插入类排序，是 将整个有序序列分割成若干小的子序列 分别进行 插入排序。 具体原理可看下图： 按照一定的规则，将数组分为多个组，然后每个组分别进行插入排序。

实现

方式一 这种方式，将数组分组后，不会处理完一组再处理一组，也就是说不会将第一小组插入排序好后再处理第二小组。它们是穿插处理的。

//希尔排序
void ShellSort(int A[],int n){
          
   
	int d,i,j,temp;
	for(d=n/2;d>=1;d=d/2){
          
   
		for(i=d;i<n;i++){
          
   //增量为i++，即各个子表交错处理 
			if(A[i]<A[i-d]){
          
   
				temp=A[i];
				for(j=i-d;j>=0&&temp<A[j];j-=d){
          
   
					A[j+d]=A[j];
				}
				A[j+d]=temp;
			}
		}
	}
}

第一趟开始，d=4，将数组分为了四个小组。按照代码，穿插处理四个小组。其实d=4感觉不到是在穿插处理，因为一组只有两个元素，意味着后面不会再碰到这一组的元素。感觉明显的还是下文的d=2。 如图的数组，穿插处理：第一个分组 第二个分组：交换38和13 第三个分组：交换 第四个分组：交换 这样第一趟，也就是d=4就处理完了。

第二趟开始，如下： d=2，把数组分为了两组。 按照代码运行，仍然是穿插处理分组。 如下处理第一个分组： 我们虽然知道76和65也是该分组的元素，但是程序只处理49和27，即按照插入排序交换两个元素。 代码继续运行，i++，即处理下一个元素。 但下一个元素就到了第二个分组中。13和49有序，不用交换。 代码继续运行，i++，又回到了第一个分组中。 27、49、76有序，执行插入排序后没有变化。 如此反复，图中的指针不断向后移动，交错处理完两个分组。 … 最后，处理完后如下图，再执行第三趟，也就是插入排序即可：

方式二 第二种方式就比较简单了，和方式一不同，不再交错处理分组。 将一个分组排好序后，再去处理下一个分组。

void ShellSort2(int A[],int n){
          
   
	int i,j,k,d,temp;
	for(d=n/2;d>=1;d=d/2){
          
   //将数组分割为多个子表 
		for(i=0;i<d;i++){
          
   //依次处理子表 
			for(j=i+d;j<n;j=j+d){
          
   //按间隔处理子表 
				if(A[j]<A[j-d]){
          
   
					temp=A[j];
					k=j-d;
					while(k>=0 && A[k]>temp){
          
   
						A[k+d]=A[k];
						k=k-d;
					}
					A[k+d]=temp;
				}
			}
		}
	}
}