希尔排序算法（基于Java实现）

2020-12-26

字数统计: 872字 | 阅读时长≈ 3分

希尔排序算法（基于Java实现）

希尔排序算法的原理与代码实现：

一、希尔排序算法的原理

因为在简单插入排序中可能会存在这样的问题，例如，我们将数组arr=[2, 3, 4, 5, 6, 1]进行排序，如果我们采用的是简单直接插入排序算法，就会发现最后一位的数字1需要移动的次数就是arr.length - 1次。这样明显就会降低排序的效率。因此，希尔排序就是为了解决这样的问题，提高直接插入排序算法的效率，应运而生的。

希尔排序的原理：

希尔排序也是一种插入排序，它是简单插入排序经过改进后的一个更加高效的版本，也称为缩小增量排序。

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

示意图如下：

二、希尔排序的代码实现

package Sort;

import java.util.Arrays;

//希尔排序
public class ShellSort {
    public static void shellSort(int[] arr){
        //增量gap，并逐步的缩小增量
        for(int gap = arr.length / 2; gap > 0; gap /= 2 ){
            //从gap个元素，逐个对其所在组进行直接插入排序
            for(int i = gap; i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j - gap]){
                    while(j -gap >= 0 && temp < arr[j - gap]){
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {23, 45, 26, 67, 89, 90, 12, 34};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        shellSort(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }
}

输出的结果：

排序前：
[23, 45, 26, 67, 89, 90, 12, 34]
排序后：
[12, 23, 26, 34, 45, 67, 89, 90]

三、希尔排序算法的性能分析

从上述的代码实现过程中，可以明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度为O(1)**，也就是，这是一个原地排序算法**。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。虽然希尔排序是插入排序的一种改进，但是由于其在插入排序之前进行一个按下标的一定增量进行分组，因此，在分组的过程中，可能在原数组中两个相同的数会分到不同的组中，因此，希尔排序算法是一种不稳定的排序算法。

希尔排序算法的时间复杂度为最好的时间复杂度为O(nlogn)。为什么时间复杂度是O(nlogn)呢？因为希尔排序刚开始就需要去分组，这一分组的操作的是O(logn)，当分完组后，再进行一次循环，就能够排好序，这是的时间复杂度不就是O(n)，而这两个循环嵌套者，故希尔排序的时间复杂度为O(nlogn)。

本文作者： feng之锋
本文链接： http://example.com/2020/12/26/希尔排序算法/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！