Dotcpp  >  编程教程  >  Java数组  >  Java希尔排序(Shell Sort)

Java希尔排序(Shell Sort)

点击打开在线编译器,边学边练

希尔排序(Shell Sort)是插入排序的一种,也是直接插入排序的更高效的改进版本,希尔排序充分利用了插入排序的两个特点:

1)当数据规模小的时候非常高效。

2)当给定数据已经有序时的时间复杂度为O(n)。


所以,Shell排序每次把数据分成若干块,来使用插入排序,而且之后在这若干个小块排好序的情况下把它们合成大一点的小块,继续使用插入排序,不停地合并小块,直到最后一个小块。


这里每次分成若干个小块是通过“增量”来控制的,开始的时候增量较大,接近n/2,从而使得分割出来接近n/2个小块,逐渐的减小“增量”,最终减小到1。


例如:

public class Main {
    public static int count = 0;
    public static void shellSort(int[] data) {
        // 计算出最大的h值
        int h = 1;
        while(h <= data.length / 3) {
            h = h * 3 + 1;
        }
        while(h > 0) {
            for(int i=h;i<data.length;i+=h) {
                if(data[i] < data[i-h]) {
                    int tmp = data[i];
                    int j = i-h;
                    while(j >= 0 && data[j] > tmp) {
                        data[j+h] = data[j];
                        j -= h;
                    }
                    data[j+h] = tmp;
                    print(data);
                }
            }
            // 计算出下一个h值
            h = (h - 1) / 3;
        }
    }
    public static void print(int[] data) {
        for(int i=0;i< data.length;i++) {
            System.out.print(data[i]+"\t");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] data = new int[]{4,6,1,9,5,8};
        print(data);
        shellSort(data);
        print(data);
    }
}


运行结果如下:

4   6   1   9   5   8  
1   4   6   9   5   8  
1   4   5   6   9   8  
1   4   5   6   8   9  
1   4   5   6   8   9



本文固定URL:https://www.dotcpp.com/course/899

上一课:

Java直接插入排序

下一课:

Java集合

Java教程
第一章 Java入门
第二章 Java运算符和表达式
第三章 Java流程控制
第四章 Java类和对象
第五章 Java子类与继承
第六章 Java接口与实现
第七章 Java内部类与异常类
第八章 Java常用实用类
第九章 Java输入输出流
第十章 Java数组
Dotcpp在线编译      (登录可减少运行等待时间)