JavaScript希尔排序算法详解与代码实现

希尔排序概述

当数据已经基本有序时，插入排序能够发挥极高的效率，甚至达到线性时间复杂度。然而，在一般情况下，插入排序的效率较低，主要原因在于它每次只能将数据元素移动一个位置。希尔排序（Shell Sort）以发明者Donald Shell的名字命名，该算法于1959年首次公布。部分旧版教科书或参考手册曾将其命名为Shell-Metzner，试图包含Marlene Metzner Norton的名字，但根据Metzner本人的澄清，她并未参与该算法的设计，因此不应将其名字列入算法名称中。

算法基本思想

希尔排序的核心思想是引入增量序列。首先选择一个小于数据总数n的整数d1作为初始增量，将整个文件记录划分为d1个组。所有相距为d1倍数的记录被归入同一组，并在各组内分别执行直接插入排序。接着，选取第二个增量d2（需满足d2 < d1），重复上述分组与排序过程。这一过程持续进行，直到最终增量dt等于1（即dt < dt-1 < … < d2 < d1），此时所有记录被合并到同一组中进行最后一次直接插入排序，排序即告完成。

从本质上讲，该方法属于一种分组插入排序策略。

代码实例一

示例1：

/**
* 希尔排序，又称递减增量排序算法，是插入排序的一种高效改进版本。需要注意的是，希尔排序属于非稳定排序算法。
 *
* 希尔排序的改进基于插入排序的两个关键性质：
 *
* 当数据几乎已经排好序时，插入排序的效率非常高，可以达到线性排序的效率。
* 然而，通常情况下插入排序效率较低，因为每次操作只能将数据移动一位。
 *
 */
function shellSort( list ) {
var gap = Math.floor( list.length / 2 );
while( gap > 0 ) {
for( i = gap; i < list.length; i++ ) {
temp = list[i];
for( j = i; j >= gap && list[j - gap] > temp; j -= gap ) {
list[j] = list[j - gap];
            }
list[j] = temp;
        }
gap = Math.floor( gap / 2 );
    }
return list;
};
// 测试代码
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
shellSort(arr);

代码实例二

示例2：

<script type="text/javascript">
//document.write("----------希尔排序，插入排序的升级,1959年shell搞出来的------当增量取的正确时，时间复杂度为n的1.3次方-------");
//document.write("<br /><br />")
//var array = new Array(12, 25, 32, 16, 18, 27, 59, 69, 36);
function shellSort(array) {
var j, i, v, h=1, s=3, k,n = array.length;
var result = "";
var count = 0;
while(h < n)
h=s*h+1;
while(h > 1) {
h=(h-1)/s;
for (k=0; k<h; k++)
for (i=k+h,j=i; i<n; i+=h, j=i) {
v=array[i];
while(true)
if ((j-=h) >= 0 && array[j] > v)
array[j+h]=array[j];
else
break;
array[j+h]=v;
         }
count++;
result += "<br />第" + count + "遍排序的结果是:";
for (var n = 0; n < array.length; n++) {
result += array[n] + ",";
          }
 }
return result;
}
//shallSort(array);
//document.write("<br /><br />");
</script>