希尔 排序

交换法

它是插入排序的增强版

 它在排序时会对原本的数据按照 /2 进行分组，直到最后一次 /2 时为1

第一层for是将这10个数进行分组

第一次10/2分5组，0和5比较，1和6比较...

第二次5/2分2组，0和2比较，1和3比较，2和4比较....

import java.util.Arrays;

public class Test {
    public static void main(String[] args){
        int[] arr= {8,9,1,7,2,3,5,4,6,0};
        int count=0;
        for(int gap=arr.length/2; gap >= 0; gap/=2) {
        	for(int i=gap; i < arr.length; i++) {
        		for (int j =i - gap; j >=0; j-=gap) {
        			if (arr[j]>arr[j+gap]) {
						arr[j] = arr[j]^arr[j+gap];
						arr[j+gap] = arr[j]^arr[j+gap];
						arr[j] = arr[j]^arr[j+gap];
					}
        		}
        	}
        	System.out.print("第"+(++count)+"次排序:");
        	System.out.println(Arrays.toString(arr));
        }
    }
}

对交换的优化->位移法（交换法+插入法）

package com.wang;

import java.util.Arrays;

public class Test {
    public static void main(String[] args){
        int[] arr= {8,9,1,7,2,3,5,4,6,0};
        int count=0;
        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]= 0&&temp < arr[j-gap]) {
						arr[j] = arr[j-gap];
						j-=gap;
					}
					arr[j]=temp;
				}
        	}
        	System.out.print("第"+(++count)+"次排序:");
        	System.out.println(Arrays.toString(arr));
        }
    }
}