苏木三少
错的不是你,而是这个世界。

<每天一个> 算法实现之希尔排序

希尔排序

算法思想:

使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。

一个h有序数组就是h给相互独立的有序数组编制在一起组成的一个数组。

官方解释:

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

实现方法:

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Scanner;
public class Shell {
    private static void exch(Comparable a[],int i,int j) {//交换元素位置
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static boolean less(Comparable v,Comparable w) {//对元素进行比较
        return v.compareTo(w) < 0;
    }
    public static void sort(Comparable a[]) {
        int N = a.length;//将a数组升序
        int h = 1;
        while(h < N/3)
            h = 3*h + 1;//1,4,13,40,121,364,1093·······
        while(h >= 1) {
            for(int i = h;i < N;i++)
                {//将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]
                    for(int j = i;j>=h && less(a[j],a[j-h]);j -= h)
                        exch(a,j,j-h);
        }
            h = h/3;
        }
    }
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        System.out.println("请输入5个数进行排序:");
        String Arrays[] = new String[5];
        for(int i = 0;i < 5;i++) {
            Scanner S = new Scanner(System.in);
            Arrays[i] = S.next();
        }
        sort(Arrays);
        for(int i = 0;i < 5;i++) {
            System.out.println(""+Arrays[i]);
        }
    }
}

 

赞(5) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » <每天一个> 算法实现之希尔排序

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约