Java实现希尔排序经典代码和算法思路

本文重点讲解Java实现希尔排序经典代码和算法思路。

简介

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法，其也是一种特殊的插入排序，即将简单的插入排序进行改进后的一个更加高效的版本，也称缩小增量排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 1、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
• 2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动1

希尔排序是先将整个待排序的序列分组排序(两两一组),待整个序列中基本有序时，再对全体记录进行依次直接插入排序。

希尔排序是非稳定排序算法,它通过比较相距指定步长的元素来进行排序，每趟比较的步长随着算法的进行而减小,直到步长等于1的最后一趟排序结束。

希尔排序算法思路图解

现在我们以序列: {8, 9, 1, 7, 2, 3, 5, 6, 4, 0} 为示例进行图解算法思路！

第1步

初始步长gap = length/2 ＝ 5，意味着将整个数组分为了5组，即[8，3]，[9，5]，[1，6]，[7，4]，[2，0]，对每组进行插入排序，得到序列：{3，5，1，4，0，8，9，6，7，2}，可以看到：3，5，4，0这些小元素都被提到前面了。

第2步

缩小增量gap = 5/2 = 2，数组被分为两组，即[3，1，0，9，7]，[5，4，8，6，2]，对这两组分别进行直接插入排序，可以看到，整个数组的有序程度更进一步了。

第3步

再次缩小增量，gap = 2/2 = 1，此时整个数组为[0，2，1，4，3，5，7，6，9，8]，进行一次插入排序，即可实现数组的有序化（仅需要简单微调，而无需大量移动操作）。

希尔排序经典代码实现

接下来我们看下如何通过java代码来实现经典的希尔排序吧：

    /**
     * 希尔排序
     * 时间复杂度：O（N^1.3~N^1.5）
     * 空间复杂度：O（1）
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length; ;
        while (gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
    }
    private static void shell(int[] array, int gap) {
        // 从小到大排序
        if(array == null) {
            return;
        }
        int tmp = 0;
        for (int i = gap; i < array.length; i++) {
            tmp = array[i];
            for (int j = i - gap; j >= 0; j -= gap) {

                // j往后走
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                    array[j] = tmp;
                } else {
                    break;
                }
            }
        }
    }

 总结

以上就是Java实现希尔排序经典代码和算法思路的全部内容，你学会了吗？

喜欢 (0)赏

【请潘老师喝杯Coffee吧！】

分享 (0)