插入排序（java）

插入排序介绍

最坏时间复杂度O(N^2)

把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。

从第二个数开始与第一个数进行比较，如果比第一个数小就把第一个数向后移，最后将那个数插入进有序的排序。

下面是排序算法

public  int[] InsertSort(int[] arr)
	{
	    int i, j;
	    int n = arr.length;
	    int key;
	 
	    //假定第一个元素被放到了正确的位置上
	    //这样，仅需遍历1 - n-1
	    for (i = 1; i < n; i++)
	    {
	        j = i;
	        key = arr[i];
	 
	        while (j > 0 && key < arr[j - 1])
	        {
	            arr[j] = arr[j - 1];
	            j--;
	        }
	 
	        arr[j] = key;
	    }
	    return arr;
	}