Fork me on GitHub

排序算法-希尔排序

algorithm/shell_sort/banner

希尔排序在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序的不同,它会首先比较距离较远的元素,而非相邻的元素。

原理

希尔排序的工作原理是,通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。

如下演示希尔排序中间隔序列是如何运行的:

algorithm/shell_sort/how-shell-sort-run

通过下面的gif图也许你会更好理解:

algorithm/shell_sort/shell-sort-demo

你可以直接进入旧金山大学的David Galles教授做的站点–用HTML5实现的各种排序算法的动画比较进行查看更加详细的演示。

相关代码

希尔排序的核心代码:

1
2
3
4
5
6
7
8
9
10
11
12

// 额外添加
this.gaps = [5,3,1];

function shellsort() {
for(var g = 0;g < this.gaps.length ; ++g){
for(var i = this.gaps[g]; i < this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp ; j -= this.gaps[g]){
this.dataStore[j] = this.dataStore[j - this.gaps[g]];
}
this.dataStore[j] = temp;
}
}

具体的代码请前往demo/algorithm/shell_sort.js

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)