希尔排序算法小记（javascript代码实现）
前言
今天做排序的时候，把希尔排序写错了。写一篇希尔排序原理惩罚自己。
1 原理概述
希尔排序是插入排序的一种改进算法。它先将一个大的待排序数列分成多个小的分组，并分别对这些小的分组使用插入排序算法。经过多轮分组与组内排序，逐步合并小的分组，最终将分组重新合并成一个有序序列。
那么怎么将一开始分出的这些小分组合并成一个完整的数列呢？规则是什么呢？客官请往下看。
2 算法描述
由于个人描述能力欠佳，为避免说的太抽象，这里我们结合实例进行介绍。
这里有一个需要进行排序的数列 arr = [88, 10, 47, 41, 39, 15, 0, 53, 6, 75]，下面我们要对它执行希尔排序。
希尔排序在对数列进行分组时，用到一个概念，我们之为“增量”。增量即为分组的步长。这里使用的是希尔增量。
希尔排序开始前，按照实际需要设定一个初始增量（我们这里设定 fraction = arr.length / 2，即增量为 5）。这样就可以将数列分组，并对每个分组执行插入排序。所有分组都执行完插入排序，视为第一轮排序完成。
让我们看看这一轮排序发生了什么：
// 排序前
[88, 10, 47, 41, 39, 15, 0, 53, 6, 75]
88 ***************** 15
**** 10 ***************** 0
******** 47 *************** 53
************* 41 *************** 6
**************** 39 ************** 75
// 排序后
[15, 0, 47, 6, 39, 88, 10, 53, 41, 75]
15 ************** 88
**** 0 **************** 10
******** 47 **************** 53
********** 6 **************** 41
************* 39 ***************** 75
在第1轮排序中，数列被分为5个分组，经过本轮排序，此时每个分组内部均为有序。
此时，将增量减小（fraction = 5 / 2，即步长为 2），重新划分数列，并对每个新的分组执行插入排序。
我们看一下这一轮排序发生了什么：
// 排序前
[88, 10, 47, 41, 39, 15, 0, 53, 6, 75]
88 **** 47 **** 39 ***** 0 **** 6
*** 10 **** 41 ***** 15 *** 53 *** 75
// 排序后
[0, 10, 6, 15, 39, 41, 47, 53, 88, 75]
0 **** 6 **** 39 **** 47 **** 88
** 10 *** 15 **** 41 **** 53 **** 75
在第2轮排序中，数列被分为2个分组，经过本轮排序，此时每个分组内部均为有序。
此时，再次减小增量（fraction = 2 / 2 ，即步长为1），重新划分数列，并对每个新的分组执行插入排序。
我们看一下这一轮排序发生了什么：
// 排序前
[0, 10, 6, 15, 39, 41, 47, 53, 88, 75]
// 排序后
[0, 6, 10, 15, 39, 41, 47, 53, 75, 88]
在第3轮排序中，数列只有一个分组，经过本轮排序，整个数列内的元素为递增排列，希尔排序算法执行完毕。
3 性能分析
3.1 稳定性
由于插入排序是将待排序元素顺次插入新的有序序列中，不会改变原数列中相同关键字元素的相对位置，所以我们说插入排序是稳定的。
希尔排序算法在进行每一轮排序时，只能保证组内元素有序，但在调整组内元素的时候，可能令分在两个组中且具有相同关键字的元素交换位置。例如：
// 对如下数组使用希尔排序，增量为希尔增量
// 第一轮排序结果如下：
// 排序前
[1, 49, 33, 49, 5, 62]
1 ******** 49
** 49 ******** 5
****** 33 ******** 62
// 排序后
[1, 5, 33, 49, 49, 62]
1 ******** 49
** 5 ******** 49
****** 33 ******** 62
在这个例子中，经过第一轮排序关键字为49的元素，在原数列中的相对位置已经发生了改变。
综上可知，希尔排序是不稳定的排序算法。
3.2 时间复杂度
希尔排序的时间复杂度是不确定的，设置不同的增量规则，会对希尔排序的性能造成很大影响。例如：在希尔增量下，希尔排序的时间复杂度为O(n2)；在Hibbard增量下，希尔排序的时间复杂度为O(n(3/2))；希尔排序时间复杂度下限为 n*log2n。
快速排序算法( O(n(log2n)) )在大规模数据情况下，通常比希尔排序表现更好，所以当数据量极大时，可以优先考虑使用快速排序代替希尔排序。但是，在确定增量的情况下，希尔排序在时间复杂度的表现通常比较稳定，极端情况的上下浮动小，因此普适性更强，可以作为排序算法的首选，在发现表现欠佳时，再考虑用其他算法替换。
4 javascript 代码实现
var arr = (function(len){
if(!len) return [0];
var arr = [];
for(var i = len; i > 0; i--) arr.push(Math.floor( Math.random() * 100 ))
return arr
})(10);
console.log("original arr : ",arr)
for(var fraction = Math.floor(arr.length / 2); fraction >= 1; fraction = Math.floor(fraction / 2)) {
for(var i = fraction; i < arr.length; i++) {
for(var j = i - fraction;j >= 0 && arr[j] > arr[j + fraction]; j -= fraction) {
var temp = arr[j];
arr[j] = arr[j + fraction];
arr[j + fraction] = temp;
}
}
}
console.log("result : ",arr)
参考资料
[1] [百度百科] 希尔排序
[2] [Foliciatarier的博客] 希尔排序增量序列简介
