手撕排序Day1--插入排序

现有一数组 arr[] = { 9,8,7,6,5,4,3,2,1 } 需将其改为升序排列。

我们可以将这个数组分为两个部分--已排序的部分和未排序的部分，而第一个元素是已经排好的。

然后再用第一个未被排序的元素n与已经排序的最后一个元素m进行比较，如果n

 之后重复这个过程直到遍历完这个数组。

元素集合越接近有序，插入排序的时间效率越高。

void InsertSort(int*arr,int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[i + 1];
		while(end>=0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;

		}
		arr[end + 1] = tmp;
	}
}