插入排序的C语言实现

插入排序是一种时间复杂度为O(N^2)，空间复杂度为O(1)的算法

算法思想：

先对数组0~0范围排序，再对0~1范围排序，再对0~2范围排序...，一直到对0~N-1范围排序，

每次排序时，看当前数字左边的那个数字是不是比当前数字大，若是，则交换；否则，说明当前范围已经有序，直接进入下一次循环

代码如下：

void swap(int* arr, int x, int y) {
	int tmp = arr[x];
	arr[x] = arr[y];
	arr[y] = tmp;
}
//插入排序
void insertsort(int* arr, int sz) {
	int i = 0, j = 0;
	for (i = 0; i < sz; i++) {
		int j = i;
		while (arr[j] < arr[j - 1]) {
			swap(arr, j, j - 1);
			j -= 1;
		}
	}
}
int main() {
	int arr[10] = { 9,2,1,5,6,0,3,8,3,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	insertsort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
		printf("%d ", arr[i]);
}