java数据结构之直接插入排序

﹏ヽ暗。殇╰゛Y 2022-04-04 04:21 227阅读 0赞

直接[插入排序][Link 1]（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增 1 的有序表。

在日常生活中，经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。例如：一组从小到大排好顺序的数据列 \{1,2,3,4,5,6,7,9,10\}，通常称之为有序列，我们用序号 1,2,3，… 表示数据的位置，欲把一个新的数据 8 插入到上述序列中。

完成这个工作的步骤：

①确定数据 “8” 在原有序列中应该占有的位置序号。数据 “8” 所处的位置应满足小于或等于该位置右边所有的数据，大于其左边位置上所有的数据。

②将这个位置空出来，将数据 “8” 插进去。

直接插入排序 (straight insertion sort) 的做法是：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了 (n-1) 趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

### 基本思想 ###

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。 \[1\]

待排序记录 R1，R2，… ，Rn–1, Rn

第一步：R1

第二步：(R1), R2

第三步：(R1 , R2), R3

……

第 j 步：(R1，R2，… ，Rj–1), Rj

……

第 n 步: (R1，R2，… ，Rn–1), Rn．

例：j=5

原有序表中关键词比 Rj 大的记录数：dj

比较次数：dj+1 移动次数： dj+2

### 算法思想 ###

算法 InsertSort (R,n)

FOR j=2 TO n DO

( // 每次将 Rj 插入到有序表 R1，…，Rj–1 中

K←Kj. R←Rj. i←j-1.

WHILE (i>0) AND (Ki>K) DO

(Ri+1←Ri.

i←i-1.)

Ri+1←R.

)

算法 InsertSortA(R, s, e)

// 引入虚拟记录, Ks-1≤min\{Ki| s≤i≤e\}

ISA1 \[逐一排序\]

FOR j=s+1 TO e DO

( i←j-1．K←Kj. R←Rj .

WHILE K<Ki DO

( Ri+1←Ri ．

i←i-1 ．)

Ri+1←R ．

)

ISA1 \[逐一排序\]

FOR j=s+1 TO e DO

( i←j-1．K←Kj . R←Rj .

WHILE K<Ki DO

(Ri+1←Ri ．i←i-l) ．

Ri+1←R )

直接插入排序的时间复杂度为 O(n2)。

### 排序方法 ###

1．简单方法

首先在当前有序区 R\[1..i-1\] 中查找 R\[i\] 的正确插入位置 k(1≤k≤i-1)；然后将 R\[k．．i-1\] 中的记录均后移一个位置，腾出 k 位置上的空间插入 R\[i\]。

注意：若 R\[i\] 的关键字大于等于 R\[1．．i-1\] 中所有记录的关键字，则 R\[i\] 就是插入原位置。

2．改进的方法

一种查找比较操作和记录移动操作交替地进行的方法。具体做法：

将待插入记录 R\[i\] 的关键字从右向左依次与有序区中记录 R\[j\](j=i-1，i-2，…，1) 的关键字进行比较：

① 若 R\[j\] 的关键字大于 R\[i\] 的关键字，则将 R\[j\] 后移一个位置；

②若 R\[j\] 的关键字小于或等于 R\[i\] 的关键字，则查找过程结束，j+1 即为 R\[i\] 的插入位置。

关键字比 R\[i\] 的关键字大的记录均已后移，所以 j+1 的位置已经腾空，只要将 R\[i\] 直接插入此位置即可完成一趟直接插入排序。

## 哨兵的作用 ##

算法中引进的附加记录 R\[0\] 称监视哨或哨兵 (Sentinel)。

哨兵有两个作用：

① 进人查找 (插入位置) 循环之前，它保存了 R\[i\]的副本，使不致于因记录后移而丢失 R\[i\]的内容；

② 它的主要作用是：在查找循环中 "监视" 下标变量 j 是否越界。一旦越界 (即 j=0)，因为 R\[0\]. 可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测 j 是否越界 (即省略了循环判定条件"j>=1")。

注意：

① 实际上，一切为简化边界条件而引入的附加结点 (元素) 均可称为哨兵。

【例】单链表中的头结点实际上是一个哨兵

② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。

## 过程实例 ##

例：

原有序表：(9 15 23 28 37) 20

找插入位置 : (9 15 ^ 23 28 37) 20

新有序表: (9 15 20 23 28 37)

java代码如下：

package 数据结构;
    
    public class zhijiecharupaixu {
       public static void sort(long arr[]){
    	   long tep;
    	   for(int i=1;i<arr.length;i++){//注意是从1开始
    		   tep=arr[i];//把每一轮循环arr[i]的值赋给tep，用来进行比较
    		   int k=i;
    		   while(k>0 && arr[k-1]>tep){//当选择的arr[i]的前面有比它大的数的时候，把那个位置的数向后移一位，然后一次循环之后将这个小的插到空出的位置
    			   
    			   arr[k]=arr[k-1];
    		   k=k-1;
    		   }
    		   arr[k]=tep;
       }
    }
    }

测试：

package 数据结构;
    
    public class Testzhijiecharupaixu {
      public static void main(String args[]){
    	  long arr[]=new long[6];
    	     arr[0]=2;
    	     arr[1]=1;
    	     arr[2]=5;
    	     arr[3]=3;
    	     arr[4]=8;
    	     arr[5]=0;
    	    zhijiecharupaixu.sort(arr);
    	     for(int i=0;i<arr.length;i++){
    	    	 System.out.println(arr[i]);
    	     }
      }
    }

输出结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfX2xpeW9uZw_size_16_color_FFFFFF_t_70][]

好啦,这次就到这里啦，有问题可以和我留言哦！

邮箱：2321591758@qq.com

其他博客的链接：

[Github个人网站][Github]      [知乎][Link 2]      [简书][Link 3]

欢迎各位访问哦，这次就到这里啦！

[Link 1]: https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfX2xpeW9uZw_size_16_color_FFFFFF_t_70]: /images/20220404/4246ef2dd21d4d5598861e399bafb7cd.png
[Github]: http://www.imlowliness.club
[Link 2]: https://www.zhihu.com/people/li-yong-ji-suan-ji/activities
[Link 3]: https://www.jianshu.com/u/6c1284ced65e