算法基础课 2.3 希尔排序

排序：

• 冒泡排序 交换
• 选择排序 求最大 最小
• 插入排序 挪动数组
• 希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一种更高效的版本 也称为缩小增量排序 ，是非稳定排序算法

public class fsak {
    // 插入排序
    public static void main(String[] args) {
        int arr[] = new int[] {3,1,5,4,2};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void shellSort(int [] arr) {
        //不断地缩小增量
        for(int interval = arr.length/2 ;interval>0;interval = interval/2) {
            for(int i=interval;i<arr.length;i=i+1) {//此处i=i+1 是往后挪一位进行分组插入
                int target = arr[i];
                int j = i-interval;
                while(j>-1&&arr[j]>target) {
                    arr[j+interval]= arr[j];
                    j-=interval;
                }
                arr[j+interval] = target;
            } 
        }
    }
}