详解Java八大经典内排序算法——希尔排序

      我们一起来看看Java八大经典内排序算法的第二位小伙伴——希尔排序！

希尔排序-排序思路

      先取定一个小于数组长度 Data.length 的整数 gap（gap = Data.length / 2）作为第一个增量，把表的全部元素分成 gap 个组，所有相互之间距离为 gap 的倍数的元素放在同一个组中，在各组内进行直接插入排序；然后，减小增量 gap（gap = gap /2），重复上述的分组和排序过程，直至增量减小为 0，即所有元素放在同一组中进行直接插入排序。

      ※说明：希尔排序每趟并不产生有序区，在最后一趟排序结束前，所有元素并不一定归位。但是每趟排序完成后，数据越来越接近有序。

希尔排序-排序实例

      设待排序的表有 10 个元素，其关键字为 {9,8,7,6,5,4,3,2,1,0}。以下为希尔排序的排序过程：

▲ 希尔排序过程

      第一趟排序时，d = 5 ，整个表被分成 5 组：（9,4），（8,3），（7,2），（6,1），（5,0），各组采用直接插入排序方法变成有序的，即结果分别为（4,9），（3,8），（2,7），（1,6）（0,5）。

      第二趟排序时，d = 2，整个表分为两组：（4,2,0,8,6）和（3,1,9,7,5），各组采用直接插入排序方法变成有序的，即结果分别为（0,2,4,6,8）和（1,3,5,7,9）。

      第三趟排序时，d = 1，整个表为一组，采用直接插入排序方法使整个数列有序，最终结果为（0,1,2,3,4,5,6,7,8,9）。

希尔排序-排序算法

希尔排序-算法分析

      时间复杂度：O(n^1.3)；

      空间复杂度：O(1)；

      稳定性：不稳定；

      复杂性：较复杂。

      今天就分享到这里啦~

      上次我们分享的直接插入排序和本次的希尔排序都是属于【插入排序】这个大类的。

      下次我们分享下一个大类【交换排序】中的冒泡排序，听到这个名字是不是感觉很奇特，敬请期待哟~