偽代碼：
image.png
排序示意圖：
image.png
我們把A[1..j-1]的這些性質(zhì)形式地表示為一個(gè)循環(huán)不變式露乏，循環(huán)不變式主要用來(lái)幫助我們理解算法的正確性。關(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
