04希尔排序
2019-06-02 本文已影响0人
BubbleM
希尔排序：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
增量的选择：在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根据增量序列的选取其时间复杂度也会有变化，这个不少论文进行了研究，在此处就不再深究；本文采用首选增量为n/2,以此递推，每次增量为原先的1/2，直到增量为1；
下图详细讲解了一次希尔排序的过程：
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
希尔排序算法的步骤：
- 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
let arr = [65, 27, 59, 64, 58];
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
console.log('定义间隔为：'+gap);
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
console.log('间隔为'+gap+'排序前：'+arr);
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
console.log('内部排序中!!调整：'+arr);
}
arr[j+gap] = temp;
console.log('需在'+(j+gap)+'位置插入'+temp+'后：'+arr);
}
console.log('排序后：'+arr);
console.log('-------------------');
}
console.log('最终结果:'+arr);
return arr;
}
shellSort(arr);
/**
定义间隔为：4
间隔为4排序前：65,27,59,64,58
内部排序中!!调整：65,27,59,64,65
需在0位置插入58后：58,27,59,64,65
排序后：58,27,59,64,65
-------------------
间隔为1排序前：58,27,59,64,65
内部排序中!!调整：58,58,59,64,65
需在0位置插入27后：27,58,59,64,65
需在2位置插入59后：27,58,59,64,65
需在3位置插入64后：27,58,59,64,65
需在4位置插入65后：27,58,59,64,65
排序后：27,58,59,64,65
-------------------
最终结果:27,58,59,64,65 */
