首页 » JavaScript » 【排序】改进排序算法:希尔(Shell)排序

【排序】改进排序算法:希尔(Shell)排序

原文 http://blog.csdn.net/Wonder233/article/details/79158147

2018-01-25 17:39:03阅读(625)

基本思想

将待排序的数组元素分成多个子序列,使得每个子序列的元素个数相对较少,然后对各个子序列分别进行直接插入排序,待整个待排序列“基本有序”后,最后在对所有元素进行一次直接插入排序。

希尔排序是对直接插入排序算法的优化和升级。

关键

采用跳跃分割的策略:将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

基本有序:小的关键字基本在前面,大的基本在后面,不大不小的基本在中间。

例如{2,1,3,6,4,7,5,8,9,}就可以称为基本有序了。但像{1,5,9,3,7,8,2,4,6}这样,9在第三位,2在倒数第三位就谈不上基本有序。

过程描述

以数组 {65,34,25,87,12,38,56,46,14,77,92,23}\{65,34,25,87,12,38,56,46,14,77,92,23\} 为例。增量初值是 n/2=6n/2=6,之后是 d=d/2=3d=d/2=3,直到 d=d/2=1d=d/2=1 终止。
【排序】改进排序算法:希尔(<a href=Shell)排序" src="http://img.blog.csdn.net/20180125112755310?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvV29uZGVyMjMz/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="这里写图片描述" title="">

实现
/* 希尔排序 */
List.prototype.ShellSort = function () {
    var i, j, k, tmp;
    var span = parseInt(this.length / 2);
    while (span >= 1) {
        for (k = 0; k < span; k++) { /* 共 span 个小组 */
            /* 组内直接插入排序,区别是:每次不是增 1 而是增加span */
            for (i = k; i < this.length - span; i += span) {
                tmp = this.L[i + span];
                j = i;
                while (j > -1 && tmp < this.L[j]) {
                    this.L[j + span] = this.L[j];
                    j = j - span;
                }
                this.L[j + span] = tmp;
            }
        }
        console.log(span);
        span = parseInt(span / 2);
    }
}
分析

希尔排序的关键:
将相隔某个“增量”的记录组成一个子序列,实现跳跃式移动,使得排序的效率提高。需要注意的是,增量序列的最后一个增量值必须等于1才行。

由于记录是跳跃式的移动,希尔排序是不稳定的。

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹