数据结构和算法-12-希尔排序

心已赠人 2022-01-06 00:39 169阅读 0赞

这一篇来学习希尔排序，希尔排序是直接插入排序的一种优化算法。

**1.希尔排序概念**

希尔排序（shell sort）是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，该方法因DL.Shell于1959年提出而得名。希尔排序是把纪录按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰好被分层一组，算法便终止。

**2.希尔排序思想**

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数\[54 26 93 17 77 31 44 55 20\]，如果我们以步长（gap=4）为4开始进行排序，我们可以通过将这列表放在有4列的表中来更好地描述算法，这样他们就应该看起来是这样（竖着的元素是步长组成）：

![20190624101959841.png][]

上面是原始需要排序的数列，现在把gap设置4，也就是这样第一次分组。

![20190624102237601.png][]

上面54下标是0，0+4 = 4， 所以54同组的下一个元素是下标为4的元素也就是77，同理77下一个元素是20.依次类推，第二组元素是26 31, 第三组元素是93 44， 第四组元素是17 55. 希尔排序就是把每一组元素采用直接插入排序算法，对元素位置交换，进行排序，第一次希尔排序之后数列为。

![20190624102647168.png][]

得到新数列，把gap设置成2，进行再一次分组。

![2019062410283734.png][]

然后把上面两组元素，采用直接插入排序算法，交换元素位置，形成新数列。

![2019062410293935.png][]

对上面这个数列，把gap设置为1，再次采用直接插入排序，最终排序完成。

根据数列元素个数，关键在于如何设置这个gap的值，这个值决定了最优情况下算法的时间复杂度。

**3.希尔排序代码实现**

python代码实现

# coding:utf-8
    
    
    def shell_sort(alist):
        """希尔排序"""
    
        n = len(alist)
        # gap取值n的一半
        gap = n // 2
        # 最后一次gap需要等于1
        while gap > 0:
            for i in range(gap, n):
                j = i
                while j > 0:
                    if alist[j] < alist[j - gap]:
                        alist[j], alist[j - gap] = alist[j - gap], alist[j]
                        j -= gap
                    else:
                        break
            # 缩短 gap步长
            gap //= 2
    
    
    if __name__ == "__main__":
        alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(alist)
        shell_sort(alist)
        print(alist)

运行结果：

[54, 26, 93, 17, 77, 31, 44, 55, 20]
    [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度分析，如果gap一上来就是等于1，那就是前面一篇的直接插入排序算法，所以最坏时间复杂度是O（n^2）, 至于什么情况下有最优的时间复杂度，这个需要数学方面知识去计算gap的取什么值才有最优解。

java代码实现过程

import java.util.Arrays;
    
    public class ShellSort {
    
        public static void main(String[] args){
            int[] arr = {54, 26, 93, 17, 77, 31, 44, 55, 20};
            System.out.println(Arrays.toString(arr));
            shellSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void shellSort(int[] arr){
            int gap = arr.length/2;
            while( gap > 0){
                for(int i = gap; i < arr.length; i++){
                    int j = i;
                    //插入排序算法核心部分
                    while(j > 0){
                        if(  j >= gap && arr[j] < arr[j - gap]){
                            int tmp = arr[j];
                            arr[j] = arr[j - gap];
                            arr[j - gap] = tmp;
                            j -= gap;
                        }else{
                            break;
                        }
                    }
                }
                gap /= 2;
            }
        }
    }

注意上面的if判断条件中多写了一个j 和gap的判断，不然报空指针错误，运行结果：

[54, 26, 93, 17, 77, 31, 44, 55, 20]
    [17, 20, 26, 31, 44, 54, 55, 77, 93]

[20190624101959841.png]: /images/20211228/6d0753f44cdd49c9aca5c0a7d6be1e6d.png
[20190624102237601.png]: /images/20211228/1bbdd221c64f4827a6a2df90b3248516.png
[20190624102647168.png]: /images/20211228/c46c19072e45403d885cc2d3349126b9.png
[2019062410283734.png]: /images/20211228/f037d9df6d01487d8b7e73b5525a9488.png
[2019062410293935.png]: /images/20211228/a3e1e5182bc74ab68e1b7a4dbc9da426.png