数据结构之希尔排序（Java）

1、基本思想
希尔排序是插入排序的一种，又称为“缩小增量排序”，插入排序对于有序的序列效率很高，但是每次只能将数据移动一位，所以一般情况下也是低效的，鉴于此，希尔排序也是直接插入排序的改进版本，比插入排序更加高效。
希尔排序实质上是一种分组插入方法，也就是说，将整个数组元素序列分割成若干个小的子序列，然后分别对子序列进行插入排序。

2、代码实现（Java语言）

package com.java;

import java.util.Scanner;

public class ShellSort {
    public static void main(String[] args) {
        System.out.println("请输入整数数组（逗号分隔）：");
        Scanner scanner=new Scanner(System.in);
        String str=scanner.next();
        String[] array=str.split(",");
        int[] arr=new int[array.length];
        for (int i=0;i<arr.length;i++){
            arr[i]=Integer.parseInt(array[i]);
        }

        System.out.print("希尔排序之前的数组：");
        printarray(arr);
        System.out.println();
 
        shellSort(arr);
        System.out.print("希尔排序之后的数组：");
        printarray(arr);
        System.out.println();
    }

    //打印数组
    public static void printarray(int[] arr){
        for (int i:arr){
            System.out.print(i+" ");
        }
    }

    public static void shellSort(int[] arr){
        int count=0;
        //设置增量k
        for (int k=arr.length/2;k>0;k/=2) {
            //对一个步长区间进行比较[step,arr.length]   插入排序
            for (int i = k; i < arr.length; i++) {
                int temp = arr[i];
                int j;

                for (j = i - k; j >= 0 && arr[j] > temp; j -= k) {
                    arr[j + k] = arr[j];
                }
                arr[j + k] = temp;
            }
            count++;
            System.out.print("第"+count+"趟排序之后的数组：");
            printarray(arr);
            System.out.println();
        }
    }
}

3、算法分析
时间复杂度为O(n^(1.3—2))，相对于插入排序来说，希尔排序的时间复杂度会比插入排序的时间复杂度好一些。
一次插入排序不会改变相同元素的相对顺序，但是在不同的插入排序过程中，相同的元素可能在各自的插入排序中改变顺序，所以希尔排序是不稳定的。

数据结构之希尔排序（Java）

原文：https://www.cnblogs.com/nothingya/p/13974138.html