11--插入排序

算法描述：从当前位置开始，从后往前找比当前数字小的，插入到这个小的数字的后面，在找的过程中，如果发现一个比当前数字大，同时将这个数字往后挪动，其中从后往前是重点。

插入排序的时间复杂度是，特别地，若完全有序则时间复杂度为

空间复杂度为，并且它是稳定的。

插入排序的特点：越有序越快

代码如下：

#include<stdio.h>

//插入排序
void InsertSort(int *arr,int len)
{
	int tmp;
	for (int i = 1; i < len; i++)//i是当前要处理的数字的下标
	{
		tmp = arr[i];
		int j;
		for (j = i - 1; j >= 0; j--)//从后往前找位置，找比当前数字小的，同时移动数据
		{
			if (arr[j] > tmp)
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + 1] = tmp;	
	}
}

//输出函数
void Show(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[] = { 7,6,2,3,1,4,5,8,9,10 };
	int len = sizeof(arr) / sizeof(arr[0]);

	InsertSort(arr, len);
	Show(arr, len);
	
	return 0;
}