使用JavaScript实现希尔排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。 工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序以次类推。
如下图所示：其中方框中的数为分组排序的数。灰底的数字为已排好的数，下划线的数为下一次排序插入的数。
|
原始数组： 22
53 72 11 34 44
11 15 28 3 10 65 第一次排序： 22 53
72 11 34 44 11 15
28 3
10 65 第二次排序： 22 53 72
11 34 44 11 15
3
28
10 65 第三次排序： 22
53 72 11 34 44
11 15 3 10 28 65 第四次排序： 11
22 53 72 34 44 11
15 3 10 28 65 …… 步长9完： 11 11 22
15 34 44 53 72
3
10 28 65 第九次排序： 11 11
22 15 34 44 53
72 3 10 28 65 第十次排序： 11 11
22 15 34 44 53
72 3 10 28 65 …… 最后趟排序： 3 10 11
11 15 22 28
34 44 53 65 72 |
function ShellSort(mData)
{
var step = new Array(9,5,2,1);
var iTemp;
var k, s, w;
for (var i = 0; i < step.length; i++)
{
k = step[i];
s = -k;
for (var j = k; j < mData.length; j++)
{
iTemp = mData[j];
w = (j - k);//求上step个元素的下标
if (s == 0)
{
s = -k;
s++;
mData[s] = iTemp;
}
while ((iTemp < mData[w]) && (w >= 0) && (w <=
mData.length))
{
mData[w + k] = mData[w];
w = w - k;
if (w < 0) break;
}
mData[w + k] = iTemp;
}
}
ShellSort = mData;
}
