原理

类似于插扑克牌的思想，保持手上的牌都是有序的，只需要把新抽的牌插入对应位置即可，从而保证了自己不断比较的部分是有序的，减少比较成本

代码实现

void sort(int *arr, int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = i; j > 0; j--)
		{
			if (arr[j] < arr[j - 1])
			{
				swap(&arr[j], &arr[j - 1]);	
			}
			else
			{
				break;
			}
		}
	}
}

优化思路

频繁的交换是没必要的，可以用个temp暂存初始位置的值，把要交换的值往后挪一位，最后在把temp赋值在最终位置上

void sortP(int* arr, int n)	//优化的算法
{
	for (int i = 1; i < n; i++)
	{
		int temp = arr[i];	//用临时变量记录初值避开两两交换

		for (int j = i; j >= 0; j--)
		{
			if (j != 0 && temp < arr[j - 1])
			{
				arr[j] = arr[j - 1];
			}
			else
			{
				arr[j] = temp;
				break;
			}
		}
	}
}

评价

是选泡插 三个简单算法里最好用的一种

对几乎有序的数组很有效