【经典排序】插入排序
插入排序
简介：
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
原理：
通过每个数位每次的前后比较，来确定两个数之间的位置关系，如果后一个数 小于 前一个数（以正序排来说），则需要进行前后互换，知道前一个数 大于 后一个数 为止。
思路：
遍历待排序数组
判断当前 第i个数 是否小于 （i-1）前一个数，如果小于则进行位置互换。
继续进行步骤②，直到 当前数字 大于 前一个数字，则停止。
然后取下一个数字（i+1）作为当前数，继续步骤② 和 步骤③。
排序结束。
示例：数组 [10,1,35,61,89,36,55]
第1个数：
10，前面没有数，完成。
第2个数：
1，前面10，1<10，交换位置；然后变成[1,10,35,61,89,36,55]，1前面已经没有数，完成。
当前顺序：[1,10,35,61,89,36,55]
第3个数：
35，10<35，无操作。
当前顺序：[1,10,35,61,89,36,55]
第4个数：
61，,35<61，无操作。
当前顺序：[1,10,35,61,89,36,55]
第5个数：
89，61<89，无操作。
当前顺序：[1,10,35,61,89,36,55]
第6个数：
36，36<89，交换位置后，36和61，比较，36<61，再次交换位置，然后36和35比较，36>35，无需交换，完成。
当前顺序：[1,10,35,36,61,89,55]
第7个数：
55，同理可得，55应该插入到36和61之间。
当前顺序：[1,10,35,36,55,61,89]
完成！
代码：
public static void sort(int[] a) {for (int i = 0; i < a.length; i++) {for (int j = i; j > 0; j--) {if (a[j] < a[j - 1]) { // 如果后一位 大于前一位，则交换位置int t = a[j];a[j] = a[j - 1];a[j - 1] = t;}}}}
还可以简洁一点
public static void sort2(int[] a) {for (int i = 0, j; i < a.length; i++) {int t = a[i];// 前向移动，直到前一位比 当前值 小for (j = i; j > 0 && t < a[j - 1]; j--) a[j] = a[j - 1];// 当前值位置a[j] = t;}}
算法分析：
稳定性：
如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变。通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的。
简单来说，如果a[i]跟a[i-1]相等的话，就不作处理，这样就是稳定的。
时间复杂度：
根据上面的分析也可以看出，第 i 个数之前是有序的话（也就是a[i] > a[i-1]），这样就只需要一次判断；但是如果数据是逆序的话，那就每次都需要做 i-1次判断和交换，所以有最好最坏情况之分。
最好情况：
数组本来就是有序的，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n-1次，时间复杂度为O(n)。
最坏情况：
数组是逆序的，此时需要比较总次数为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n²)。
平均情况：
平均来说，A[1..j-1]中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，也就是O(n²)。
空间复杂度：
O(1)，没有其他辅助空间。
优缺点：
在小数据量的情况下，插入排序是很有效的排序方法。因为小数据量的时候，最好情况O(n)和最坏情况O(n²)，差别不大的，都是很快就会完成。
那为什么不用快排或者归并呢，O(nlogn）不是应该更快么？
因为小数据量的时候，最好情况和最坏情况都差别不大很快；而且这是一个原地排序法，没有额外的内存开销，也没有快排归并那种递归涉及到栈的开销；而且计算的次数比较少，每次只有一次判断或者外加一次数据交换。
所以插入排序的最坏情况可能还要比其他排序的最好情况还要快。这也是为什么Java的Arrays.sort()《》方法在数据量少于47的时候使用插入排序。
我怎么令自己开心都不知道，但却想去哄你开心