数据结构——插入排序（直接插入排序，希尔排序java）二.希尔排序

50 阅读 0 评论 33 点赞

我是靠谱客的博主秀丽服饰，最近开发中收集的这篇文章主要介绍数据结构——插入排序（直接插入排序，希尔排序java）二.希尔排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一.直接插入排序：

1、基本思想

直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。对于给定的一组记录，初始时假定第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直到最后一个记录插到有序序列中为止。

2、复杂度分析

当最好的情况，也就是要排序的表本身就是有序的，此时只有数据比较，没有数据移动，时间复杂度为O(n)。
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：2+3+…+n=(n+2)(n-1)/2 次,而记录移动的最大值也达到了 (n+4)(n-1)/2 次.
如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为次 $frac{n^{2}}{4}$ ，因此，得出直接插入排序发的时间复杂度为 $O(n^{2})$ 。从这里可以看出，同样的是时间复杂度 $O(n^{2})$ ，直接插入排序法比冒泡和简单选择排序的性能要好一些。

3、排序过程如下

以数组{38,65,97,76,13,27,49}为例，
这里写图片描述

public class InsertSort {
    public static void insertSort(int[] a) {
        int i, j, insertNote;// 要插入的数据
        for (i = 1; i < a.length; i++) {// 从数组的第二个元素开始循环将数组中的元素插入
            insertNote = a[i];// 设置数组中的第2个元素为第一次循环要插入的数据
            j = i - 1;
            while (j >= 0 && insertNote < a[j]) {
                a[j + 1] = a[j];// 如果要插入的元素小于第j个元素,就将第j个元素向后移动
                j--;
            }
            a[j + 1] = insertNote;// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
        }
    }

    public static void main(String[] args) {
        int a[] = { 38,65,97,76,13,27,49 };
        insertSort(a);
        System.out.println(Arrays.toString(a));
    }
}

二.希尔排序

1、基本思想：

希尔排序也成为“缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序。因此，我们要采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。希尔排序是对直接插入排序算法的优化和升级。
所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，例如｛2,1,3,6,4,7,5,8,9,｝就可以称为基本有序了。但像｛1,5,9,3,7,8,2,4,6｝这样，9在第三位，2在倒数第三位就谈不上基本有序。

2、复杂度分析：

希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外，由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
希尔排序最好时间复杂度和平均时间复杂度都是 $Oleft ( nlogn right )$ ，最坏时间复杂度为 $O(n^{2})$ 。

3、排序过程如下：

以数组{26, 53, 67, 48, 57, 13, 48, 32, 60, 50 }为例，步长序列为{5,2,1}
初始化关键字： [26, 53, 67, 48, 57, 13, 48, 32, 60, 50 ]

这里写图片描述

最后的排序结果：
13 26 32 48 48 50 53 57 60 67

public static void shellSortSmallToBig(int[] data) {
        int j = 0;
        int temp = 0;
        for (int increment = data.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < data.length; i++) {             
                temp = data[i];
                for (j = i - increment; j >= 0; j -= increment) {
                    if (temp < data[j]) {
                        data[j + increment] = data[j];
                    } else {
                        break;
                    }
                }
                data[j + increment] = temp;
            }
            for (int i = 0; i < data.length; i++)
                System.out.print(data[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] data = new int[] { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };
        shellSortSmallToBig(data);
        System.out.println(Arrays.toString(data));
    }

转载：https://blog.csdn.net/jianyuerensheng/article/details/51258460