插入排序（直接插入、希尔）

女爷i 2023-07-24 13:28 1阅读 0赞

## 直接插入排序 ##

##### 排序策略 #####

**在有序表的恰当处插入一个新元素，并保持该有序表的有序性**  
即，当插入第n个元素时，前n-1个元素已经是有序排列

##### 排序过程 #####

以集合\{49, 38, 65, 97, 76, 13, 27, 49\}中数据为例

①初始存储  
![在这里插入图片描述][20200412113716315.png]  
②第一趟（插入38）  
![在这里插入图片描述][20200412113754493.png]  
③第二趟（插入65）  
![在这里插入图片描述][2020041211385091.png]  
③第三趟（插入97）  
![在这里插入图片描述][20200412113924324.png]  
④第四趟（插入76）  
![在这里插入图片描述][20200412114013609.png]  
⑤第五趟（插入13）  
![在这里插入图片描述][20200412114105506.png]  
⑥第六趟（插入27）  
![在这里插入图片描述][20200412114235407.png]  
⑦第七趟（插入49）  
![在这里插入图片描述][20200412114325154.png]  
一共有八个数据，执行了七次插入操作，即对于长度为n的列，需执行n-1趟  
插入数据的过程：  
从已排好序的数据尾进行判断，若要插入的数据小于当前数据，则该数据后移，指针前移，判断前一位，若要插入的数据大于当前数据，则保存数据，完成插入

##### 实现代码 #####

/**
      * 插入排序
      * @param list 需要排序的行列
      * @return 排序结果
      */
     public static int[] inSort(int[] list) {
      	//需执行n-1次
      	for(int i = 1; i < list.length; i++) {
       		int add = list[i];
       		int index = i-1;
       		//和已经排序完成的片段进行判断新插入的数据位置
       		//此处可用监视哨代替越界判断
       		for(; index >=0; index--) {
        			if(list[index] < add) {
         				break;
        			}else {
         				//移动数据
         				list[index+1] = list[index];
        			}  
       		}
      		//插入数据
       		list[++index] = add; 
      	}
      	return list;
     }

**测试结果**  
![在这里插入图片描述][2020041212103656.png]

##### 时间及空间复杂度 #####

①时间（使用移动次数和比较次数作为衡量标准）  
**最好**，原先序列为正序：比较次数![在这里插入图片描述][20200412121944292.png]、移动次数 0  
**最坏**，原先序列为倒序：比较次数![在这里插入图片描述][20200412122250726.png]即(n\*(n+1))/2 - 1、移动次数![在这里插入图片描述][20200412122112289.png]即((n+1)\*(n+2))/2 - 3（每次都得添加到序列头部）

即平均时间复杂度为：T(n)=O(n2)

②空间  
在移动时不需要另外访问存储空间，所以空间复杂度：  
S(n)=O(1)

③稳定性  
在线性表中逐一比较，所以该算法是稳定的

##### 适用范围 #####

①n较小  
②局部有序

## Shell排序 ##

希尔排序（Shell’s Sort）又叫“缩小增量排序”，是对直接插入排序所作的改进

##### 排序策略 #####

**先将整个待排序的记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序**  
即，对表中数据进行分组，对每个组进行排序，分组方式：n/(2^i)

##### 排序过程 #####

以集合\{59,20,17,13,28,14,23,83,36,98,11,70,65,41,42,15\}中的数据为例

①第一趟，d=16/2=8  
![在这里插入图片描述][20200412155046963.png]  
②第二趟，d=8/2=4  
![在这里插入图片描述][20200412155324193.png]  
③第三趟，d=4/2=2  
![在这里插入图片描述][20200412155522124.png]  
④第四趟，d=2/2=1  
![在这里插入图片描述][20200412155618918.png]  
⑤结果  
![在这里插入图片描述][20200412155655151.png]

##### 实现代码 #####

/**
      * 希尔排序
      * @param list 需要排序的数据
      * @return 排序的结果
      */
     public static int[] sheSort(int[] list) {
      	//设置步长,进行分组
      	int step = list.length/2;
     	while(step >= 1) {
       		//i每走一步会变换一个组
       		for(int i = step; i<list.length; i++) {
        			//记录当前数据
        			int add = list[i];
       			//定位该组中前一个数据索引
        			int j = i-step;
        			//对每个组内的数据进行插入排序
        			//后移数据，查询插入位置
        			while(j >= 0 && list[j] > add) {
         				list[j+step] = list[j];
         				j = j - step;
        			}
        			list[j+step] = add;
       		}
       		//缩小步长，继续分组
       		step = step/2;     
    	  } 
    	  return list;
     }

**测试结果**  
![在这里插入图片描述][20200412160116640.png]

##### 时间及空间复杂度 #####

**因为增量d的存在，使记录不像在直接插入排序中一步步地向前移，而是跳跃式地向前移动，使整个排序的效率得到了改善**  
①时间（跟步进策略有关）  
**最好**：原先序列为正序，步长d=1，即：T(n) = O(n)  
**最坏**：若步进策略为`/2`时，若序列为\{1、k、2、k+1、…、k、2k\}（k=n/2，n为2的整数幂）时，只有当步长d=1时，才会排序，这时退化为直接插入排序，交换次数为:1+2+…+k-1 = (k\*(k-1))/2 = (n\*(n-2))/8  
即：T(n) = O(n2)

即平均时间复杂度为：T(n) = O(n\*log2n)  
②空间  
S(n) = O(1)  
③稳定性  
不稳定  
        由于Shell排序是分组进行排序，它是跳跃式的向前移动，会导致原来在后面的关键字移到前面，使两个相等的关键字进行排序后的顺序会被改变

[20200412113716315.png]: /images/20230528/d13be27aab474d83a28da7d2c6c58682.png
[20200412113754493.png]: /images/20230528/0739ffbd89ae496fb45d20292c83fc60.png
[2020041211385091.png]: /images/20230528/b95d5be32dc1446788426ec9adc13d22.png
[20200412113924324.png]: /images/20230528/b4ee43ca53af4b7fa79ff35bfa2871d4.png
[20200412114013609.png]: /images/20230528/d8aaa21422944353afd96cb9a0383d99.png
[20200412114105506.png]: /images/20230528/e6dfc9b35b124d48995d0d6bf30397b1.png
[20200412114235407.png]: /images/20230528/b0950935b7c34f0a8ddffbe0d61ab187.png
[20200412114325154.png]: /images/20230528/29d5070f48a0496e9bf846160e0ba281.png
[2020041212103656.png]: /images/20230528/91e72b11bc334807887679aecc206882.png
[20200412121944292.png]: /images/20230528/2d524bb2a930427689a9f2c2a99118a4.png
[20200412122250726.png]: https://img-blog.csdnimg.cn/20200412122250726.png
[20200412122112289.png]: /images/20230528/919432eccab345d88cf752a48fde6692.png
[20200412155046963.png]: /images/20230528/17e42243c6624fff848a134026e3315d.png
[20200412155324193.png]: /images/20230528/5d056792871e4501b82133a2cb44d6ce.png
[20200412155522124.png]: /images/20230528/65b416505b5444aa8e212e280fcfa95f.png
[20200412155618918.png]: /images/20230528/3fe084b55d9c46538d2638180cfcf2a9.png
[20200412155655151.png]: /images/20230528/48fd611bbfe74ea49038b429cdfccd45.png
[20200412160116640.png]: /images/20230528/53534479ab3b4cf086cc4e89b2ffc7dc.png