?前言?：

算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！

?前言?：

?插入排序的思想?

💎如何进行插入💎

??💎插入的具体方法💎

??插入排序具体代码的实现?

?时间复杂度的计算?

?插入排序的思想?

💡：插入排序的核心思想就是插入二字，理解要如何插入和其内在的逻辑对深刻理解插入排序至关重要。

💎如何进行插入💎

🔑：我们假设要对n个数进行插入排序，那么我们的步骤是，先让下标0~0上有序（只有一个数显然成立），我们再把下标为1的数插入进这个有序序列中去让0~1上有序，而我们要实现0~2上有序，只需要让2位置的数插入到0~1上（这时0~1上的数相对顺序不变，其还是有序的，让2位置的数插入到应该在的位置），以此类推，最后一次时，下标为0~n-2上所有数都已经有序了，只需要将下标为n-1的元素插入到0~n-2这个有序序列中去。从这样的逻辑分析，每次我们让后面一个数插入时，前面所有数都已经有序，由这样的逻辑分析下去最后一定让所有数全部有序。

??💎插入的具体方法💎

🔑上文讲了插入排序的全部过程，但并没有细致的讲具体是如何进行插入的，其实插入的过程只有一个步骤：

? ? ?比如我们现在想要让0~n上排成升序，由上述可知，此时0~n-1上一定已经有序，我们插入的时候不能改变原本0~n-1上所有元素的相对顺序，只需要让n位置的元素向左看与它相邻的元素，如果n位置的元素比左边的小，就让两个元素进行交换，然后这个元素继续与左边的元素比较，如果小就交换，直到它比左边元素大或者左边没有元素时才会停下来。

💡:插入的步骤可以简化为4个字（看比换停）。

讲到这里相信大家对插入排序的大致思路显然已经十分清晰了，如果大家胸有成竹，请大家先自己写一篇，再过来看看我写的代码，这样效果最好。

??插入排序具体代码的实现?

#include<stdio.h>
void Swap(int arr[], int i, int j)
{
	//两种方法
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
	
	//arr[i] = arr[i] ^ arr[j];
	//arr[j] = arr[i] ^ arr[j];
	//arr[i] = arr[i] ^ arr[j];
}
void insertionSort(int arr[], int sz)
{
	for (int i = 1; i < sz; i++)//控制插入排序的范围即0-1....0-n-1
	{
		for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--)
		{
//满足两个条件才交换
//1:小于左边的数
//2:没有越界

			Swap(arr, j, j + 1);
		}
	}
}