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;
				}
			}
		}
	}
}
经验分享 程序员 微信小程序 职场和发展