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; } } } } }
下一篇:
万丈高楼平地起——写在开博时