首页 > 代码库 > 经典排序算法--希尔排序

经典排序算法--希尔排序

算法简介

  希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序。

白话理解:

  我们依然已排队为例,加入队伍中,有一些小个子站在了队伍的后面,而一些大个子又站在了队伍的前面,这是如果再使用插入排序,那就太没有效率了。通常情况下,老师会先看一眼,然后将后面的小个子和前面的大个子互换位置。当这个队伍顺序差距不是特别明显后,再使用插入排序。

  但是计算机没办法一眼看出来哪些元素差距比较大,于是我们可以每趟排序,根据对应的增量,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。(例子不是特别贴切...,暂时想不到更好的例子...)

例如:

  技术分享

 

Java代码实现:

 1 package sortDemo;
 2 
 3 /**
 4  * 插入代码实现
 5  * @author xianyu
 6  * @CreatTime 下午8:16:11
 7  */
 8 public class shellDemo {
 9     
10     public static void main(String[] args) {
11         int[] sort ={3,2,1,4,6,5,8,9,10,7} ;
12         System.out.println("排序前:");
13         print(sort);
14         shellSort(sort);
15         System.out.println("\n排序后:");
16         print(sort);
17     }
18     
19     
20     /**
21      * 直接插入算法排序
22      * @param a
23      */
24     public static void shellSort(int[] a){
25         
26         //确定一个增量h,网上的一些说法,认为这种情况效率比较高,然后我并不知道为什么。。。
27         int h = 1;
28         int len = a.length;
29         while(h<len/3){
30             h = h*3+1;
31         }
32         while(h>0){
33             int in,out;
34             for ( out = h;out < a.length; out++) {
35                 int tmp = a[out];
36                 for ( in = out-h; in>=0&&a[in]>tmp; in=in-h) {
37                     a[in+h]=a[in];
38                 }
39                 a[in+h] = tmp;
40             }
41             h=(h-1)/3;
42         }
43     }
44     
45     public static void print(int[] a){
46         for (int i = 0; i < a.length; i++) {
47             System.out.print(a[i]+" ");
48         }
49     }
50 }

算法分析

希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

经典排序算法--希尔排序