最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

十大经典排序8:希尔排序思路

XAMPP相关 admin 174浏览 0评论

希尔排序思路:

希尔排序也是一种插入排序(对插入排序不熟的同学可以看十大经典排序–插入排序及其优化

由于插入排序不管数组分布如何,在排序过程中总是一步一步的对元素进行比较,移动,插入,比如[5,4,3,2,1,0]这种倒序序列,数组末端的0要回到首位置很是费劲,比较和移动元素均需n-1次

基于这种情况,希尔排序采用跳跃分组的方式,现将原数组按某个跨度分组,然后对每个分组进行插入排序,这样的话后面的元素就能直接交换插入到前面去,之后再缩小跨度、分组、插入排序直至跨度为1,完成整个排序

 

题外话:希尔与插入排序的不同之处在于,它会优先比较距离排序较远的元素,这样可以大大减少远处数据插入到前面所需要的移动次数

 

为什么叫希尔排序?

  • 因为这个方法是一个叫希尔的大哥提出的

drf41

算法步骤:

  1. 设定一个原始跨度k,将原数组分组,第一组元素下标为[0, 0+k, 0 + 2k…],第二组元素下标为[1, 1+k, 1+2k…],依次类推
  2. 对每组元素进行插入排序
  3. 缩小跨度k,重复1、2操作,直至k = 1,数组变成一个组,再对这个组进行排序即可

这里找来一张图方便大家理解:里面的增量就是上面描述的跨度

drf041

代码:

 1public static void sort(int[] arr) {
 2    //设置跨度gap,每次循环缩小gap
 3    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
 4        //从第gap个元素,逐个对其所在组进行直接插入排序操作
 5        for (int i = gap; i < arr.length; i++) {
 6            int j = i;
 7            while (j - gap >= 0 && arr[j] < arr[j - gap]) {
 8                //插入排序采用交换法
 9                swap(arr, j, j - gap);
10                j -= gap;
11            }
12        }
13    }
14}
15
16//这里交换数组元素采用类似异或法的思想
17// 有兴趣同学可以玩玩异或法实现
18private static void swap(int arr[], int i, int j) {
19    arr[i] = arr[i] + arr[j];
20    arr[j] = arr[i] - arr[j];
21    arr[i] = arr[i] - arr[j];
22}

时间复杂度:O(n1.3~n2) 

空间复杂度:O(1)

以上仅是个人思路解法,觉得还不错欢迎点赞关注分享

转载请注明:XAMPP中文组官网 » 十大经典排序8:希尔排序思路

您必须 登录 才能发表评论!