希尔排序

1.基本概念:

是一种插入排序,简单插入排序的改进版本又名缩小增量排序.

为什么叫做希尔排序?因为叫做希尔提出这种的算法

2.算法思想

1.按照跳跃式策略,把数据列按下标的一定增量分组,然后对每组使用直接插入排序算法排序

2.随着增量逐渐减少,继续按组进行插入排序操作,每组包含的数据个数越来越多,当增量减至1时,整个文件被分成一个组.数据在进行一次插入排序,(基本是微调,即可)

3.图解说明

首先看下动态图(网上找的,与下文数组不符合,看过程)

1.原始数组:下面的数据元素颜色相同的为一组

2.初始化希尔增量: gap=len>>2即分为五组(这个希尔增量不是最优的,只是举例)

[8,3],[9,5],[1,4],[7,6],[2,0]

3.对这五组分别进行直接插入排序,从图中可以看出如3,5,6,0的小元素都调到前面了

接下来继续缩小增量gap/2(相当于5/2=2),机分为两组(仔细看里面的分组)

[3,1,0,9,7],[5,6,8,4,2]

4.继续对上面的两组进行直接插入排序,如下图,此时整个数组有序程度更进一步

再继续缩小增量 gap/2,此时整个数组为1组啦,看到没有?基本有序了

5.最后一步:进行微调,(再调用下直接插入排序),大功告成!

4.代码实现

public  void  shell_sort(int[] nums){
    //判断是否合法
    if(nums==null) return;
    //数组长度
    int len=nums.length;
    //初始化希尔增量
    int gap;
    int i,j;
    //这里以len/2为希尔增量的标准
    for(gap=len/2;gap>=1;gap/=2){
        //对分组的成员进行直接插入排序
        for(i=gap;i<len;i++){
            //设置临时哨兵,记录每个分组的末尾元素值
            int temp=nums[i];
            //按照增量的间隔进行遍历比较
            for(j=i-gap;j>=0&&temp<nums[j];j-=gap){
                //如果后面的元素比前面的元素小,进行调换
                nums[j+gap]=nums[j];
            }
            //j+gap:就是每个分组的末尾元素
            nums[j+gap]=temp;
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

第二个版本【采用交换法】

package 七大排序;

/**
 * 按照希尔增量进行分组,并对每组的元素进行直接插入排序
 * 然后希尔增量逐渐减少,每减少一次,分一次组,并进行每组的直接插入排序
 * 直至增量为1,在进行一次直接插入排序(基本微调),就到实现了希尔排序
 * 时间复杂度: O(n)--O(n^2)
 * 空间复杂度:O(1)
 */

public class ShellSort {
    public  void  shell_sort(int[] nums){
        if(nums.length==0)  return;
        //定义全局变量:希尔增量,i,j,temp(哨兵)
        int gap,i,j,k,temp;
        int len=nums.length;
        for(gap=len/2;gap>0;gap/=2){
            //遍历每组元素,判断是否交换
            for(i=gap;i<len;i++){

                for(j=i-gap;j>=0;j-=gap){
                    if(nums[j]>nums[j+gap]){
                        swap(nums[j],nums[j+gap]);
                    }
                }
            }
        }
    }

    private void swap(int a, int b) {
        a=a^b;
        b=a^b;
        a=a^b;

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

第三个版本【】

public void  shell_sort2(int[] arr){
        System.out.println("Start===================");
        for (int gap= arr.length/2; gap >0 ; gap/=2) {
            for (int i = gap; i<arr.length; i++) {
                //哨兵
                int j=i;
                int temp=arr[i];
                if(arr[j]<arr[j-gap]){
                   while (j-gap>=0&&temp<arr[j-gap]){
                       arr[j]=arr[j-gap];
                       j-=gap;
                   }
                   arr[j]=temp;
                }
                
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.时空复杂度

时间复杂度:O(n)~O(n^2)

控件复杂度:O(1)