偽代碼：

image.png

排序示意圖：

image.png

我們把A[1..j-1]的這些性質(zhì)形式地表示為一個(gè)循環(huán)不變式，循環(huán)不變式主要用來幫助我們理解算法的正確性。關(guān)于循環(huán)不變式，我們必須證明三條性質(zhì)：

• 初始化：循環(huán)的第一次迭代之前，它為真。
• 保持：如果循環(huán)的某次迭代之前它為真，那么下次迭代之前它仍為真。
• 終止：在循環(huán)終止時(shí)，不變式為我們提供一個(gè)有用的性質(zhì)，該性質(zhì)有助于證明算法是正確的。

JAVA代碼實(shí)現(xiàn)：

Integer[] arr = {15, 22, 41, 16, 11, 31};
for (int i = 1; i < arr.length; i++) {
      System.out.println(arr[i]);
      int key = arr[i];
      int j = i - 1;
      while (j >= 0 && arr[j] > key) {
          arr[j + 1] = arr[j];
          j = j - 1;
      }

      arr[j + 1] = key;
}

輸出結(jié)果：

image.png