插入排序之直接插入排序，折半插入，希尔排序详解和特点

我就是我 2022-05-12 03:08 196阅读 0赞

插入排序引申了三种：直接插入排序，折半插入排序，希尔排序

## **一、直接插入排序** ##

### **直接插入排序排序方法:** ###

1、查找出L(i)在L\[1……i-1\]中的位置k。

2、将L\[k……i-1\]所有元素全部后移一个位置。

3、将L(i)复制到L(k)。

### **直接插入排序排序过程：** ###

![70][]

**//\*\*\*\*\*\*\*\*\*\*直接插入排序的伪代码\*\*\*\*\*\*\*\*\*\*\*\*\*\*\***

void InsertSort(ElemType A[],int n){
    		int i,j;
    		for(i=2;i<=n;i++){
    			if(A[i].key<A[i-1].key){
    				temp=A[i];			//赋值为哨兵，作为比较元素
    				for(j=i-1;temp<A[j].key;--j){		//从后往前查找到要插入的位置
    					A[j+1]=A[j];					//元素后移
    				}
    				A[j+1]=temp;					//插入元素
    			}
    		}
    	}

**//\*\*\*\*\*\*\*\*\*\*直接插入排序的代码实例\*\*\*\*\*\*\*\*\*\*\*\*\*\*\***

package com.sort;
    /**
     * 直接插入排序
     * @author pshdhx
     *
     */
    public class InsertSort {
    	public static void main(String[] args) {
    		int a[]= {3,65,334,68,45,89};
    		int i,j;
    		for(i=2;i<a.length;i++) {
    			if(a[i]<a[i-1]) {
    				int temp=a[i];
    				for(j=i-1;temp<a[j];--j) {
    					a[j+1]=a[j];
    				}
    				a[j+1]=temp;
    			}
    		}
    		for(int w=0;w<a.length;w++) {
    			System.out.print(a[w]+" ");
    		}
    	}
    }

### 直接插入排序性能分析： ###

![70 1][]

### **二、折半插入** ###

//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*折半查找实例： \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

package com.sort;
    /**
     * 折半插入排序
     * @author pshdhx
     *
     */
    public class BubbleInsertSrot {
    	public static void main(String[] args) {
    		int a[]= {3,65,334,68,45,89,23,44};
    		int i,j,low,high,mid;
    		for(i=2;i<a.length;i++){
    			int temp=a[i];
    			low=1;
    			high=i-1;
    			while(low<=high){
    				mid=(low+high)/2;
    				if(a[mid]>temp){
    					high=mid-1;			//查找左半子表
    				}else{
    					low=mid+1;			//查找右半子表
    				}
    			}
    			for(j=i-1;j>=high+1;--j){
    				a[j+1]=a[j];
    			}
    			a[high+1]=temp;
    		}
    		for(int w=0;w<a.length;w++) {
    			System.out.print(a[w]+" ");
    		}
    	}
    }

###  三、希尔排序 ###

先将待排序表分割成若干个形如L\[I,i+d,i+2d,……i+kd\]的子表，分别进行直接插入排序，当整个表中元素已呈基本有序时，再对全体记录进行一次直接插入排序。希尔排序的排序过程如下:

先取一个小于 n的步长d，把表中全部记录分成d1个组，所有距离为d1的倍数的记录的在同一个组中，在各组中进行直接插入排序;然后取第一个步长d2<d1，重复上述过程，直到所有到的d=1,即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有性，故可以很快得到最终结果。

d1=n/2，d2=d1/2;直到最后一个增量等于1。

**实例分析：**

第一趟增量为5，直接插入排序第1，6个元素，第2，7个元素，第3，8个元素，第4，9个元素，第5，10个元素

第二趟增量为3，直接插入排序第1，3，6，9个元素，第2，5，8个元素，第7，10个元素进行排序

第三趟增量为1，直接插入排序第1到10个元素进行排序。

![70 2][]

### **实例分析代码：** ###

package com.sort;
    /**
     * 希尔排序
     * @author pshdhx
     *
     */
    public class ShellSort {
    	public static void main(String[] args) {
    		int a[]= {50,26,38,80,70,90,8,30,40,20};
    		int dk;
    		int i,j;
    		for(dk=a.length/2;dk>=1;dk=dk/2){		//步长变化,实际上共有dk个分组进行插入排序
    			for(i=0;i<dk;i++) {					//分别对每个dk分组进行排序
    				for(j=i+dk;j<a.length;j+=dk) {
    					if(a[j]<a[j-dk]) {
    						int temp=a[j];
    						int k = j - dk;
    	                    while (k >= 0 && a[k] > temp){
    	                        a[k + dk] = a[k];
    	                        k -= dk;
    	                    }
    	                    a[k + dk] = temp;
    					}
    				}
    			}
    			
    		}
    		for(int w=0;w<a.length;w++) {
    			System.out.print(a[w]+" ");
    		}
    	}
    }

### 性能分析： ###

空间效率：仅仅使用了常数个辅助单元，空间复杂度为o(1)

时间效率：由于其是依赖于增量函数的排序，在某个特定范围内，希尔排序的时间复杂度约为o(n^1.3)，最坏情况下时间复杂度为o(n^2)。

稳定性：在划分字表的同时，会造成元素相对位置的变化，因此是不稳定的。

适用性：希尔排序算法仅仅适用于当线性表为顺序存储的情况。

[70]: /images/20220512/c883339777204fc5873d64d589a22250.png
[70 1]: /images/20220512/4fb6ea77c0e94bf88374bbeac54f0c0e.png
[70 2]: /images/20220512/c4ba05fd33d0493cb7a4ec62b9a5f1b5.png