C语言插入排序（直接插入排序）

直接插入排序：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

时间复杂度:O(N^2);
空间复杂度:O(1);
稳定性：稳定排序
应用场景：序列接近有序或者元素个数较少的情况

动图演示

void InsertSort(int arr[], int size) 
{
    
    //i不能<=size-1；否则不稳定
	for (int i = 1; i < size-1; i++)
	{
    
		int end = i-1;
		int key = arr[i];
		//end>=0，防止数组越界
		while (end >=0 && arr[end] > key)
		{
    
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end+1] = key;
	}
}