希尔排序

来自计算思维百科
跳转至: 导航搜索
希尔排序1.png

如果我们希望对很多数据按照从小到大或是从大到小的顺序重新放置,这就是排序。希尔排序是把数据按下标的一定增量分组,对每组使用直接插入排序算法排序;然后减小增量,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个数据就排序好了。

基本概念

希尔排序的基本思想是:通过将待排序的元素分为若干个子序列,利用直接插入排序思想对子序列进行排序。然后将该子序列缩小接着对子序列进行直接插入排序。按照这种思想,直到所有的元素都按照关键字有序排列。

具体算法实现:假设待排序的元素有n个,对应的关键字分别是a1,a2,a3…an,设距离(增量)为c1=4的元素为同一个子序列,则元素的关键字a1,a5,…ai,a(i+5),….为一个子序列,同理,关键字a2,a6,…a(i+1),a(i+6),..,a(n-4)为一个子序列。然后分别对同一个字序列的关键字利用直接插入排序进行排序。之后,缩小增量c2=2,分别对同一个子序列的关键字进行插入排序。依次类推,最后令增量为1,这时只有一个子序列,对整个元素进行排序。

应用范围

所有需要进行排序的应用领域都可使用希尔排序。

使用方法及步骤

  1. 确定初始增量;
  2. 根据增量将数据划分为若干个子序列;
  3. 每个子序列按照插入排序进行排序;
  4. 减小增量,重复步骤1-3;直至只有一个子序列。

应用案例

应用1- 实例排序

案例:首先要明确一下增量的取法:

第一次增量的取法为: d=count/2;

第二次增量的取法为:  d=(count/2)/2;

最后一直到: d=1;

看上图观测的现象为:

d=3时:将40跟50比,因50大,不交换。

    将20跟30比,因30大,不交换。

    将80跟60比,因60小,交换。

d=2时:将40跟60比,不交换,拿60跟30比交换,此时交换后的30又比前面的40小,又要将40和30交换; 将20跟50比,不交换,继续将50跟80比,不交换。

d=1时:这时就是前面讲的插入排序了,不过此时的序列已经差不多有序了,所以给插入排序带来了很大的性能提高。

希尔排序2.png

应用2-选手分组

案例:有50位选手去参加比赛,每个人的衣服上都有一个编号,已按编号排好,现在要将这50名选手按身高从低到高排好,有什么方法可以给这50位选手快速排序呢?

在这里,我们可以先让编号是5的倍数(5,10,15…)的选手出列,10个人快速按身高排好,按现在的次序插入原来的空位,即现在10个人最矮的站到5号空位,依次类推,

接着让编号是4的倍数(4,8,12…)的选手出列,排序,再入列;接着重复步骤,让编号是3,2,的选手也按照前面的方法来排,最终50位选手就按身高从低到高排好了。

可以体现的计算思维

希尔排序将数据进行分组,每个组完成同样的插入排序,然后重复这个过程,体现了计算思维的递归思想。