深入浅出排序算法之希尔排序

简介: 深入浅出排序算法之希尔排序

1. 原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

(1)希尔排序是对直接插入排序的优化。

(2)当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

 

2. 代码实现

//希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;//增量是多少都可以,随便小伙伴们写
        }
        shell(array,1);
    }
    //有增量的直接插入排序
    //不是一组希尔排序全部排完,是间隔性的,可能是第一组先插一个,第二组再插一个,第一组再插……
    private static void shell(int[] array,int gap){
        for(int i = gap;i < array.length;i++){
            int tmp = array[i];
            int j = i - gap;
            for(;j >= 0;j -= gap){
                if(array[j] > array[j+gap]){
                    array[j + gap] = array[j];
                }
                else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    public static void main(String[] args) {
        int[] arr = {3,1,2,4,5};
        Sort.shellSort(arr);
        for (int x : arr) {
            System.out.print(x + " ");
        }
    }

3. 性能分析

时间复杂度 空间复杂度
最好 平均 最坏
O(N) O(N^1.3) O(N^2) O(1)
数据有序 难以构造出来
public static void main(String[] args) {
        int[] arr2 = new int[10000];
        Test.createArray2(arr2);
        long s2 = System.currentTimeMillis();
        Sort.insertSort(arr2);
        long e2 = System.currentTimeMillis();
        System.out.println("直接插入排序的数组逆序的情况:"+(e2 - s2));
        int[] arr1 = new int[10000];
        Test.createArray2(arr1);
        long s1 = System.currentTimeMillis();
        Sort.shellSort(arr2);
        long e1 = System.currentTimeMillis();
        System.out.println("希尔排序的数组逆序的情况:"+(e1 - s1));
    }

稳定性:不稳定。

由于增量不同,可能导致本来在后面的元素跑到前面去!

相关文章
|
6月前
|
算法 搜索推荐 Java
数据结构与算法(Java篇)笔记--希尔排序
数据结构与算法(Java篇)笔记--希尔排序
|
29天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
18 1
|
5月前
|
算法 搜索推荐
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
|
4月前
|
算法 搜索推荐 Shell
|
5月前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
33 0
|
5月前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
43 0
|
5月前
|
搜索推荐
排序算法---希尔排序---详解&&代码
排序算法---希尔排序---详解&&代码
|
5月前
|
算法 Shell C语言
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
53 0
|
6月前
|
存储 算法 搜索推荐
【数据结构与算法】:插入排序与希尔排序
欢迎大家来到初阶数据结构的最后一小节:排序
【数据结构与算法】:插入排序与希尔排序
|
6月前
|
搜索推荐 算法 Shell
【数据结构与算法】直接插入排序和希尔排序
【数据结构与算法】直接插入排序和希尔排序