排序算法的详细介绍(六) -- 希尔排序

常见排序算法归档介绍:

希尔排序 Shell Sort

算法描述

先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序.
然后取 d2(d2 < d1).
重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序.
一般选 d1 约为 n/2, d2 为 d1 /2, d3 为 d2/2 ,…, di = 1.

shell_sort_animation

实例分析

数组: [80, 93, 60, 12, 42, 30, 68, 85, 10], 排序过程:
首先取 d1 = 4, 将数组分为 4 组, 如下图中相同颜色代表一组:
然后分别对 4 个小组进行插入排序, 排序后的结果为:
然后，取 d2 = 2, 将原数组分为 2 小组:
然后分别对 2 个小组进行插入排序, 排序后的结果为:
最后, 取 d3 = 1, 进行插入排序后得到最终结果:

代码实现

function shellSort(array) {
    function swap(array, i, k) {
        var temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }
    var length = array.length,
        gap = Math.floor(length / 2);
    while (gap > 0) {
        for (var i = gap; i < length; i++) {
            for (var j = i; 0 < j; j -= gap) {
                if (array[j - gap] > array[j]) {
                    swap(array, j - gap, j);
                } else {
                    break;
                }
            }
        }
        gap = Math.floor(gap / 2);
    }
    return array;
}

此文参考于 bubkoo.com,十分感谢.
所有引用内容版权归原作者所有.
使用知识共享“署名-非商业性使用-相同方式共享 3.0 中国大陆”许可协议授权.

常见排序算法归档介绍:

希尔排序 Shell Sort

算法描述

实例分析

代码实现

CATALOG

FEATURED TAGS