演算法導論-插入排序

• 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