直接插入排序：
该算法属于原址排序，算法在数组A中重排这些数，在任何时候，最多只有其中的常数个数存储在数组外面。
在运行完函数insertion_sort(A)后，输入数组A包含排序好的输出序列。
插入排序类似于排序扑克牌。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入到左手中的正确位置。
算法中：
下标j指出正被插入到手中的“当前牌”，比如上图的梅花7。此时j=4。在for循环（循环变量j）的每次迭代的开始，元素A[0..j-1]的子数组构成了当前排序好的左手中的牌（如上图中的2/4/5/10）。剩余的子数组A[j+1...len(A)-1]对应于仍在桌子上的牌堆。事实上，元素A[0..j-1]就是原来在位置[0..j-1]的元素，但现在已按序排列。
A[j]依次和A[0..j-1]的每个元素作比较（while循环）。
如果发现A[i]比key大，那么A[i]后移(就是A[i]中存放的值放到下一个位置啦)，即A[i+1] = A[i]（本来比较大的元素就应该往后嘛）这样，大的元素一直往后往后……
直到，找到一个元素A[i]（比如上图的5）比key(上图中的7)小，那么while循环中的语句执行不了了。而元素A[i]的下一个元素A[i+1]因为比key大已经后撤了，那么A[i+1]即是存放key的正确位置啦~~~
然后就是再次从桌子上取牌啦，即j增加。
def insertion_sort(A): for j in range(1,len(A)): key = A[j] #Insert A[j] into the sorted sequence A[0..j-1]. i = j-1 while i>=0 and A[i]>key: A[i+1] = A[i] i = i-1 A[i+1] = key运行：
>>> A=[31,41,59,26,41,58] >>> insertion_sort(A) >>> A
[26, 31, 41, 41, 58, 59]
若输入数组已排好序，则是最好情况。最好情况时间复杂度为O(n)。
若输入数组已反向排序，即按递减排序排好序，则导致最坏情况。最坏情况时间复杂度 O(n^2) 。
package chapter1; import java.util.Arrays; public class Insertion_sort { public static void main(String[] args) { // TODO Auto-generated method stub int [] A={22,1,3,43,2,6,19}; System.out.println(Arrays.toString(insertion_sort(A))); } public static int[] insertion_sort(int [] A){ for (int j = 1; j < A.length; j++) { int key=A[j]; int i=j-1; while(i>=0 && A[i]>key){//A[i]大于key，而不是A[j]。i应该大于等于0。而不是大于0 A[i+1]=A[i]; i--; } A[i+1]=key;//等于key,而不是A[j] } return A; } }
