首页 > 代码库 > 希尔排序总结
希尔排序总结
数据结构之排序算法——希尔排序
代码很多地方借鉴了 http://my.csdn.net/MoreWindows 他的思想,
本人认为该作者已经写的很好了,只是在他的基础上加入了一些自己的理解和说明
如果涉及到版权的问题,请联系我的邮箱,我会尽快删除
希尔排序想关链接:
维基百科: https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F#C.E8.AA.9E.E8.A8.80
百度百科:http://baike.baidu.com/view/178698.htm
参考博客 :http://blog.csdn.net/morewindows/article/details/6668714
希尔排序:其实就是分组的插入排序
希尔排序基本思想是:
在无序的数组中定义一个增量,然后用增量将数组分成几个部分,每个部分进行插入排序,然后减少增量的大小,继续进行插入排序,直到最后增量为1,进行最后的排序操作
我看到两种增量的定义方式
第一种是 先将数组的长度赋值3/1 +1给增量,然后让增量等于自己的3/1 +1,保证每次增量的大小不小于 1,结束条件是增量不小于 1
注意: 使用这个方式一定要注意增量是永远大于等于1 的,因此一个好的处理方式是使用do {}while();
第二种是将数组将数组的长度除以2赋值给增量,然后让增量等于自己的1/2 结束条件是增量小于1
其实增量的定义只是在分组的时候,确定每个组数据的规模,没什么需要去深究的!
利用第一个增量方式的源码:
void Shell_Sort(int array[], int arrayLen)
{
// 定义一个增量
int Incremental = arrayLen;
do
{
Incremental = Incremental / 3 + 1;
for (int i = 0; i < Incremental;++ i)
{
for (int j = i + Incremental; j < arrayLen; j += Incremental)
{
// 从大到小
if (array[j - Incremental] < array[j])
{
int InsertNum = array[j];
int k = j-Incremental;
while (k >= 0 && array[k] < InsertNum)
{
array[k+ Incremental] = array[k];
k -= Incremental;
}
array[k + Incremental] = InsertNum;
}
}
}
} while (Incremental > 1);
}
利用第二个增量方式的源码
void Shell_Sort(int array[], int arrayLen)
{
// 确认每次增量的大小
for (int Incremental = arrayLen / 2; Incremental > 0; Incremental /= 2)
{
// 分组进行插入排序
for (int i = 0; i < Incremental; ++ i)
{
for (int j = i + Incremental; j < arrayLen; j+= Incremental)
{
// 从大到小
if (array[j - Incremental] < array[j])
{
int InsertNum = array[j];
int k = j-Incremental;
while (k >= 0 && array[k] < InsertNum)
{
array[k + Incremental] = array[k];
k -= Incremental;
}
array[k + Incremental] = InsertNum;
}
}
}
}
}
针对第二种方案的一些优化:主要是对开始位置的优化,在插入排序中,每次查找与前面的大小关系时都从已经有序的位置开始,在希尔排序的每个分组里面我们也可以这样认为,这样,我们每次从增量开始,寻找增量和它前面的分组的数的关系,然后进行大小的调整
源码如下
void Shell_Sort(int array[], int arrayLen)
{
for (int Incremental = arrayLen / 2; Incremental > 0; Incremental /= 2)
{
// 分组进行插入排序
for (int i = Incremental; i < arrayLen; ++ i)
{
// 由大到小
if (array[i] > array[i - Incremental])
{
int InsertNum = array[i];
int j = i - Incremental;
// 注意分析 j 和 InsertNum 代表的数据的位置,结合整体的大小顺序
while (j >= 0 && array[j] < InsertNum)
{
array[j + Incremental] = array[j];
j -= Incremental;
}
array[j + Incremental] = InsertNum;
}
}
}
}
还可以进一步把第二次优化的的最后的一个for(){}和下面的if()语句合并,然后用数据的移动来代替,查找插入位置
源码:
void Shell_Sort(int array[], int arrayLen)
{
for (int Incremental = arrayLen / 2; Incremental > 0; Incremental /= 2)
{
// 分组进行插入排序
for (int i = Incremental; i < arrayLen; ++i)
{
for (int j = i - Incremental; j >=0 && array[j] < array[j + Incremental]; j -= Incremental)
{
Swap_IntVal(array + j, array + j + Incremental);
}
}
}
}
希尔排序总结