经典算法之希尔排序（Shell‘s Sort）

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

1. 概念

希尔排序，又称为缩小增量排序，是一种非稳定的排序算法。那希尔排序怎么进行缩小增量呢，首先把所要排序的序列按下标的一定增量分组，对每组使用直接插入排序算法进行排序，随着增量逐渐减少，每组包含的元/素越来越多，当增量减至1时，整个文件恰被分成一组，至此算法结束。
算法思想
先将要排序的一组数按某个增量d分成若干个组，每组中记录的下标相差d，对每组中全部元素进行排序，然后再用一个较小的增量对其进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，至此排序结束。
一般情况下，初始取序列的一半作为增量，以后每次减半，直到增量1。假如，总共有十个元素，那么增量序列的取值依次为：5、2、1

2.伪代码

d = A.length / 2
while d > 0
    for i = 1 to d
        for j = i + d to A.length by d
            tmp = A[j]
            k = j - d
            while k > 0 and A[k] > tmp
                A[k + d] = A[k]
                k = k - d
            A[k + d] = tmp
    d = d / 2
1
2
3
4
5
6
7
8
9
10
11

3. 核心代码实现

3.1 Java版

public static void main(String[] args){
    int[] array={49,38,65,97,76,13,27,49,78,34};
    System.out.println("排序之前：");
    for(int i=0;i<array.length;i++){
        System.out.print(array[i]+" ");
    }
    //希尔排序
    int gap = array.length;
    while (true) {    
        gap /= 2;   //增量每次减半    
        for (int i = 0; i < gap; i++) {        
            for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序                       
                int k = j - gap;            
                while (k >= 0 && array[k] > array[k+gap]) {
                    int temp = array[k];
                    array[k] = array[k+gap];
                    array[k + gap] = temp;                
                    k -= gap;            
                }                
            }    
        }    
        if (gap == 1)        
            break;
    }
 
    System.out.println();
    System.out.println("排序之后：");
    for(int i=0;i<array.length;i++){
        System.out.print(array[i]+" ");
    }
}
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

3.2 Python版

def shell_sort(seq):
    seq_len = len(seq)
    step = seq_len >> 1
    # 增量小于1说明最终排序已完成
    while step:
        for i in range(step, seq_len):
            # j记录元素原始位置，用于查找前面所有小于当前元素的元素
            j = i
            while seq[j] < seq[j-step] and j-step >= 0:
                seq[j], seq[j-step] = seq[j-step], seq[j]
                # 改变下标，查看前面是否还有更小的值
                j -= step
        print(f"增量{step}的排序：", seq)
        # 每次增长减小一半
        step = step >> 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. 算法效率分析

希尔排序的执行时间依赖增量序列。好的增量序列的共同特征：

• 最后的增量必须为1
• 尽量避免序列中的值互为倍数的情况。

空间复杂度为：O(1)
时间复杂度为：O(n^（1.3—2）)