算法-插入排序

基本思想

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。

实现原理

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5
7. 时间复杂度 O(n^2) 空间 O(1)，稳定排序，原地排序

void insertSort(vector<int>& nums)
{
	for ( int i = 1; i < nums.size(); ++i )
	{
		if ( nums[i] < nums[i - 1] )
		{
			int j = i - 1;
			int x = nums[i];
			while ( j >= 0 && x < nums[j] )
			{
				nums[j + 1] = nums[j];
				j--;     //元素后移
			}
			nums[j + 1] = x;     //插入到正确位置
		}
	}
}