排序---希尔排序实现和性能分析

短命女 2023-07-05 14:45 8阅读 0赞

## 希尔排序 ##

希尔排序是简单插入排序的改进，直接插入排序的最坏情况时间复杂度达到O(n^2)，比如从大到小的一串数字654321，使用插入排序从小到大进行排序，这就达到插入排序的最坏情况。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

#### 示意图 ####

（1）对下面这组数据进行从小到大排序（n个）  
![在这里插入图片描述][20200215194140747.png]  
（2）初始增量gap=n/2  
![在这里插入图片描述][20200215194151729.png]  
（3）对上面的5组进行插入排序得到结果如下，再进行分组 gap=gap/2  
![在这里插入图片描述][20200215194202921.png]  
（4）直到gap=1，整个数据基本有序  
![在这里插入图片描述][20200215195207305.png]  
（5）再进行最后一次插入排序  
![在这里插入图片描述][20200215195408537.png]

#### 实现 ####

public class ShellSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            shellSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
    
        public static void shellSort(int[] arr) { 
            int length = arr.length;
    
            //每次分组间隔较小一半
            for(int gap = length / 2; gap > 0; gap = gap /2) { 
                for(int i = gap; i < length; i++) { 
                    //将第i个元素插入分组中的正确位置
                    insert(arr, gap, i);
                }
            }
        }
    
        //直接插入法
        public static void insert(int[] arr, int gap, int i) { 
            int item = arr[i]; //当前要插入的元素
            int index = i - gap;
    
            while(index >= 0 && item < arr[index]) { 
                arr[index + gap] = arr[index];
                index -= gap;
            }
    
            arr[index + gap] = item;
        }
    }

## 性能分析 ##

**1. 时间复杂度**  
希尔排序的复杂度和增量序列是相关的，增量序列就是上面举例中gap的序列（5,21），而增量序列也可以用其他算法，有的增量序列的复杂度至今还没有证明出来

\{1,2,4,8,…\}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)

Hibbard提出了另一个增量序列\{1,3,7，…,2k-1\}，这种序列的时间复杂度(最坏情形)为O(n1.5)

Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是\{1,5,19,41,109,…\}  
**2. 空间复杂度为O(1)**  
**3. 稳定性**  
虽然插入排序是稳定的，但是希尔排序**不是稳定的**，因为希尔排序在插入元素的时候是跳跃性插入，有可能破坏稳定性，如7 5 5 8，第一次分组之后，两个5在不同的两组中，第一组的5会和7交换使得两个5最终的前后顺序发生了改变

[20200215194140747.png]: https://img-blog.csdnimg.cn/20200215194140747.png
[20200215194151729.png]: https://img-blog.csdnimg.cn/20200215194151729.png
[20200215194202921.png]: https://img-blog.csdnimg.cn/20200215194202921.png
[20200215195207305.png]: https://img-blog.csdnimg.cn/20200215195207305.png
[20200215195408537.png]: https://img-blog.csdnimg.cn/20200215195408537.png