<img src=”https://timgsa.baidu.com/timg…;quality=80&size=b9999_10000&sec=1541245646279&di=70b2cfd6752b26aa4e9cb04579c8dd6a&imgtype=0&src=http%3A%2F%2Fwww.psahz.com%2Fuploads%2Fallimg%2F181006%2F094Q62X3-2.jpg” width=”100%” hegiht=”20%” align=center />
== 算法主要衡量标准 ==
时间复杂度（运行时间）
在算法时间复杂度维度，我们主要对比较和交换的次数做对比，其他不交换元素的算法，主要会以访问数组的次数的维度做对比。
其实有很多同学对于算法的时间复杂度有点模糊，分不清什么所谓的 O(n),O(nlogn),O(logn)… 等，也许下图对一些人有一些更直观的认识。
空间复杂度（额外的内存使用）
排序算法的额外内存开销和运行时间同等重要。就算一个算法时间复杂度比较优秀，空间复杂度非常差，使用的额外内存非常大，菜菜认为它也算不上一个优秀的算法。
结果的正确性
这个指标是菜菜自己加上的，我始终认为一个优秀的算法最终得到的结果必须是正确的。就算一个算法拥有非常优秀的时间和空间复杂度，但是结果不正确，又有什么意义呢？
== 原理 ==
每次在无序的列表中取一个元素插入到一个有序列表的适当位置，成为一个元素加 1 的新的有序列表。。插入排序根据原理又分为 直接插入排序、二分插入排序、希尔排序等，今天主要讲一下直接插入排序。直接插入排序是一种稳定的排序算法
假设排序顺序从左至右，具体步骤如下：
列表第一个元素和前面元素比较，如果小于前面元素（其实不存在），则交换位置。（这步其实可以没有）
列表第二个元素和前面元素（第一个元素）比较，如果小于前面元素，则交换位置。
列表第三个元素和前面元素（第二个元素）比较，如果小于前面元素，则交换位置。如果和前面元素交换了位置，现在在第二个位置上，则接着继续和前面元素比较（第一个元素），如果小于前面元素，接着再次交换位置，然后再次重复比较过程 ….
… 继续重复以上过程，直到最后一个元素完成比较
比较移动过程中，如果元素不需要移动意味着该元素排序完毕。
++ 网络上的插入排序大多都是新建一个有序列表用来存放最终结果，其实在无序列表上进行排序操作空间复杂度才更优 ++
也许一张更直观的图比上千句话效果都好：
== 复杂度 ==
时间复杂度
比较次数
对于长度为 N 的主键不重复的列表，插入排序 平均情况下需要 n²/ 4 次比较，最坏情况下需要 n²/ 2 次比较，最好的情况下需要 n -1 次比较。
交换次数
对于长度为 N 的主键不重复的列表，插入排序平均情况下需要 n²/ 4 次交换，最坏情况下需要 n²/ 2 次交换，最好情况下需要 0 次交换。
== 性能和特点 ==
总体来说，直接插入排序是一种比较简单的排序算法，很容易理解也很好用代码实现，当然他的特点也很明显：
运行时间和数据初始状态有关
插入排序的思想是把一个元素插入一个有序的列表中，假如这个元素的位置正好是有序部分的末尾呢？也就是说当前元素不用移动位置。再一次假如整个列表都是有序的会发生什么情况呢？根本就不需要移动任何元素。这也就是为什么在最好的情况下交换次数为 0，比较次数为 n - 1 的原因。
假如列表的很大一部分元素是有序的，插入排序可能比大多数排序算法都要快。
== 适用场景 ==
直接插入排序对于小型列表或者非随机元素列表很有效。例如：部分元素有序。大体可归纳为：
每个元素距离自己的最终位置都不远。
一个有序的大列表连接一个小列表。
列表中只有少数元素不正确。
== 其他 ==
为什么插入排序是稳定呢？
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有 1 个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
== 实现案例 ==
c
static void Main(string[] args)
{
List<int> data = new List<int>() ;
for (int i = 0; i < 10; i++)
{
data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));
}
// 打印原始数组值
Console.WriteLine($” 原始数据：{string.Join(“,”, data)}”);
int n = data.Count;
// 此处可以直接从第二个元素开始
for (int i = 1; i < n; i++)
{
// 查找最小的元素的索引
for (int j = i; j>0 ; j–)
{
if (data[j] < data[j – 1])
{
// 异或法 交换两个变量，不用临时变量
data[j] = data[j] ^ data[j-1];
data[j-1] = data[j] ^ data[j – 1];
data[j] = data[j] ^ data[j – 1];
}
}
}
// 打印排序后的数组
Console.WriteLine($” 排序数据：{string.Join(“,”, data)}”);
Console.Read();
}
运行结果：
原始数据：72,78,42,60,84,74,60,79,72,52 排序数据：42,52,60,60,72,72,74,78,79,84
Go
家里没环境，还得翻墙，以后再补上吧，望见谅。
独乐不如众乐
我表弟在追学校的一个女生，每天短信无数，可那妞从来都不回他。我对他说：骚年！女人的天性只是八卦和好奇心！就你这样还想泡妞呢！看你表哥的！我用他手机给那妞发：你是我们学校三大美女之一，但我只喜欢你。半分钟之后，那妞就回了：另外两个是谁，你为什么只喜欢我啊？
<img src=”https://timgsa.baidu.com/timg…;quality=80&size=b9999_10000&sec=1541252359891&di=deecf761d736d3a2fab178e7e1a4d519&imgtype=0&src=http%3A%2F%2Fimg2.dzwww.com%3A8888%2Ftupian%2F20170927%2F201709270938c7cfcb55355b15.jpg” align=center />
添加关注，查看更精美版本，收获更多精彩