01_插入排序
#include<stdio.h>void insert_sort(int arr[], int n);
void printArray(int arr[], size);int main()
{int arr[] = {1, 2, 3, 22, 5, 9};int n = sizeof(arr) / sizeof(arr[0]);printf("打印原始數組:\n");prinfArray(arr, n);insert_sort(arr, n);printf("打印排序后的數組: \n");
}void insert_sort(int arr[], int n)
{int i, key, j;for(i = 1; i < n; i++){key = arr[i];j = i -1;while(j >= 0 && arr[j] > key){arr[j+1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}void printArrray(int arr[], int size)
{int i;for (i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");
}
分析
notion
循環不變式：
循環不變式是在每次循環迭代開始時都保持為真的條件。通過證明循環不變式在每次迭代中都成立，我們可以證明算法在終止時得到正確的結果
-
初始化：
循環的第一次迭代之前，不變式成立。這通常是在進入循環之前的一些初始條件或初始化步驟
-
保持：
證明如果在某次迭代開始時不變式成立，那么在這次迭代結束后仍然成立。這涉及證明循環體的執行不會破壞不變式
-
終止：
證明當循環終止時，不變式結合循環終止條件能推出算法的正確性。也就是說，不變式和終止條件共同表明算法已經得到了正確的結果
插入排序中的循環不變式
-
初始化：
在第一次迭代中，子數組arr[0]只包含一個元素，它顯然是已排序的。因此，循環不變式在循環開始前成立
-
保持：
假設某次迭代開始，子數組arr[0, … i-1]是已經排序的(即不變式成立)；
那么然后在這次迭代中，算法會將arr[i]插入到已排序的子數組arr[0, … i-1]中，使得子數組arr[0, … i]依舊是已經排序的；
通過內部的while循環，算法會找到適當的位置插入arr[i], 并保持已經排序部分的順序不變，因此，在這次迭代結束后，子數組arr[0, …i]是已經排序的(即循環不變式依舊保持)；
-
終止：
當循環終止時，‘i’ 達到了’n’, 即整個數組arr[0, … n-1]都是已拍尋的。此時，循環不變式結合終止條件表明整個數組是已排序的，從而證明算法的正確性
)
