1. 算法简介
希尔排序是一种基于插入排序而改进的一种排序算法。插入排序对于近乎有序的序列,排序效率非常高,可以达到线性排序的效率。但对于其他的情况,每次只能移动一位的插入排序效率是非常低的,基于次产生了希尔排序。
2. 算法思想
基于此产生了希尔排序,希尔排序是对序列按照下标的一定增量进行分组,对每一组使用直接插入排序(初始增量比较大,每组的元素较少,序列近乎有序)。又有然后逐渐减小增量,每组元素个数增多,继续对每组使用直接插入排序(由于之前进行过插入排序,故现在每组也是近乎有序的),当增量减小为1时,整个序列变都是有序的,排序终止。
算法动画演示
动画演示解释
首先选择增量gap = 10/2 = 5,序列按照增量5,被划分为5组,按颜色划分分别为【 8 , 3 】,【 9 , 5 】,【 1 , 4 】,【 7 , 6 】,【 2 , 0 】
对上面5组分别进行插入排序,排序后序列变为 3、5、1、6、0、8、9、4、7、2 ,可以看到,这五组中的相对小元素都被调到前面了。
继续缩小增量gap = 5/2 =2, 整个序列被分为2组 【3 , 1 , 0 , 9 , 7 】,【 5 , 6 , 8 , 4 , 2 】
分别对上面两组进行插入排序,排序后的序列变为 0、1、3、7、 9、 2、 4、 5、 6、 8
再缩小增量 gap = 2/2 = 1,然后对序列进行插入排序,即完成了整个序列的排序。
代码实现
// 讲arr[i]插入到所在分组的对应位置上 gap为增量
void InsertI(int arr[],int gap,int i)
{
int j;
int temp = arr[i];
for(j = i-gap;j>=0 && arr[i]<arr[j];j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
// 对arr[n]数组进行希尔排序
void ShellSort(int arr[],int n)
{
for(int gap = n/2;gap>0;gap/=2){
for(int i=gap;i<n;i++){
InsertI(arr,gap,i);
}
}
}
以上希尔排序的增量是采用每次减半得到的,实际上这种增量并不是一定是最优的。希尔排序针对不同的数据可能会有不同的增量模型,在这里不做过多的介绍,基本原理都是一样的。