算法导论-插入排序

• 2019 年 10 月 4 日
• 笔记

最近重新翻开算法导论宝典，打算重新温习一下，顺便记录下自己的点滴。导论中都是用的伪代码进行描述，我们这里直接用java代码进行

导论第一章是描述一些算法的作用，我们这里直接忽略，下面就直接进入算法部分

第二章第一节插入排序

插入排序又是增量排序

算法如下：

//另一种插入算法  public void sortArrs(){      int len = arrs.length;      int temp = 0;      int n = 0;      //进行len-1次循环，每次循环都将下标为i的元素插入到它前面已经排好序的队列中      for(int j=1;j<len;j++) {          if (arrs[j] < arrs[j - 1]) {              temp = arrs[j];              int i = j - 1;              n++;              while (i > 0 && arrs[i] > temp) {                  arrs[i + 1] = arrs[i];                  i--;                  n++;              }              arrs[i + 1] = temp;          }      }  }

算法复杂度：n^2