今天學(xué)習(xí)了希爾排序，他的主要思想借用了合并排序的思想。不過(guò)他不是左邊一半右邊一半，而是按照步長(zhǎng)來(lái)分，隨著步長(zhǎng)減少，分成的組也越少。然后進(jìn)行各組的插入排序。主要思路就是這樣，我在百度百科的博客園找到了其相關(guān)學(xué)習(xí)資料,附上連接：
http://baike.baidu.com/view/178698.htm
http://www.cnblogs.com/nokiaguy/archive/2008/05/16/1199359.html
所以就不用寫思路了哦，真笨，語(yǔ)文也得好好學(xué)學(xué)，不然組織語(yǔ)言的能力太差了。呵呵。
奉上源代碼(因?yàn)槭亲约簩懙?，所以還是貼一下)：
#include <stdio.h>
#include <stdlib.h>
//對(duì)單個(gè)組排序
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要排序的數(shù)據(jù)， nLen數(shù)據(jù)的個(gè)數(shù)
int ShellSort(int* pnData, int nLen)
{
//以nStep分組，nStep每次減為原來(lái)的一半。
for (int nStep = nLen / 2; nStep > 0; nStep /= 2)
{
//對(duì)每個(gè)組進(jìn)行排序
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}; //創(chuàng)建10個(gè)數(shù)據(jù)，測(cè)試
ShellSort(nData, 10); //調(diào)用希爾排序
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}