今天学习了希尔排序,他的主要思想借用了合并排序的思想。不过他不是左边一半右边一半,而是按照步长来分,随着步长减少,分成的组也越少。然后进行各组的插入排序。主要思路就是这样,我在百度百科的博客园找到了其相关学习资料,附上连接:
http://baike.baidu.com/view/178698.htm
http://www.cnblogs.com/nokiaguy/archive/2008/05/16/1199359.html
所以就不用写思路了哦,真笨,语文也得好好学学,不然组织语言的能力太差了。呵呵。
奉上源代码(因为是自己写的,所以还是贴一下):
#include <stdio.h>
#include <stdlib.h>
//对单个组排序
int SortGroup(int* pnData, int nLen, int nBegin,int nStep)
{
for (int i = nBegin + nStep; i < nLen; i += nStep)
{
//寻找i元素的位置,
for (int j = nBegin; j < i; j+= nStep)
{
//如果比他小,则这里就是他的位置了
if (pnData[i] < pnData[j])
{
int nTemp = pnData[i];
for (int k = i; k > j; k -= nStep)
{
pnData[k] = pnData[k - nStep];
}
pnData[j] = nTemp;
}
}
}
return 1;
}
//希尔排序, pnData要排序的数据, nLen数据的个数
int ShellSort(int* pnData, int nLen)
{
//以nStep分组,nStep每次减为原来的一半。
for (int nStep = nLen / 2; nStep > 0; nStep /= 2)
{
//对每个组进行排序
for (int i = 0 ;i < nStep; ++i)
{
SortGroup(pnData, nLen, i, nStep);
}
}
return 1;
}
int main()
{
int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //创建10个数据,测试
ShellSort(nData, 10); //调用希尔排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}