十大排序算法（二）插入排序

前言：插入排序也叫"插牌法"排序；

算法：

1tmp记录第n个元素，并将第n个元素设为空位；（n>1）

2依次用前n个元素 ，和tmp比较；如果tmp比他们小，将他插入此位置，此时空位前移，再重复循环之至比到第一个位置；

核心代码：

k标记位置；tmp保存元素；a[j+1]=a[j];元素前移；

时间复杂度：

最好O(n),平均 O(n^2),最坏O(n^2);

#include "iostream"
using namespace std;
void Insert_sort(int arr[], int length)
{
	if (arr == nullptr || length <2)
	{
		return;
	}
	for (int i = 1; i < length; i++)
	{
		int k = i;//待插入位置
		int tmp = arr[k];//元素保存出来；
		for ( int j = i-1;  j>=0  ; j-- ) // 
		{
			if ( tmp < arr[j])
			{
				arr[j + 1] = arr[j];// 元素后移
				k = j;//k插入的位置发生变换
			}
		}
		arr[k ] = tmp;//元素插回
	}
 }
int main()
{
	int arr[] = { 2,6,5,1,3,4,  };
	int length = sizeof(arr) / sizeof(*arr);
	Insert_sort(arr, length);
	for (int i = 0; i < length; i++)
		cout << arr[i] << " "；
	return 0;
}

我们可以对代码进行改进；

因为之前的都是有序的，如果tmp比n之前的某数还小，则一定比前面的小！

也就是:如果tmp<arr[j]，因为arr[j]之前是从小到大有序已经排好了，则一定小于arr[j]之前的，无需比较;

#include "iostream"
using namespace std;
void Insert_sort2(int arr[], int length)
{
	if (arr == nullptr || length < 2)
	{
		return;
	}
	for (int i = 1; i < length; i++)
	{
		int k = i;
		int tmp = arr[k];
		for (int j = i - 1; (j >= 0) && (tmp<arr[j] ) ; j--) //如果tmp<arr[j] ，无需比较
		{
			arr[j + 1] = arr[j];
			k = j; 
		}
		arr[k] = tmp;
	}
}
int main()
{
	int arr[] = { 2,6,5,1,3,4,  };
	int length = sizeof(arr) / sizeof(*arr);
	 Insert_sort2(arr, length);
	for (int i = 0; i < length; i++)
		cout << arr[i] << " ";
	return 0;
}