八大排序之插入排序—希尔排序

╰半夏微凉° 2022-05-14 13:41 156阅读 0赞

**`八大排序之插入排序—希尔排序`**  
算法步骤：  
1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；  
2）按增量序列个数k，对序列进行k 趟排序；  
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

时间复杂度：  
在最优的情况下，时间复杂度为：O（n ^ (1.3) ） （元素已经排序好顺序）  
在最差的情况下，时间复杂度为：O（n ^ 2）；

希尔排序也是一种插入排序方法,实际上是一种分组插入方法。

基本思想：  
1、先取定一个小于n的整数d1作为第一个增量，把表的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；  
2、 然后取第二个增量d2（＜d1），重复上述的分组和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。

代码1：

public class ShellSort {
    	public static void main(String[] args) {
    		int[] arr = {12,3,12,54,65,761,2,65,76,223};
    		ShellSort ss = new ShellSort();
    		ss.shellSort(arr);
    		System.out.println("排序后的数组为：");
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}
    	
    	//希尔排序，先对数组进行分段直接插入排序，之后再对整个较为有序的数组进行排序
    	public void shellSort(int[] arr){
    		for (int gap = arr.length/2; gap > 0; gap/=2) {
    			for (int i = gap; i < arr.length; i++) {
    				if (arr[i] < arr[i-gap]) {
    					int temp = arr[i];
    					int j;
    					for (j = i-gap; j >=0 && arr[j] > temp; j-=gap) {
    						arr[j+gap] = arr[j];
    					}
    					arr[j+gap] = temp;
    				}
    			}
    		}
    	}
    }