插入排序

插入排序

基本思想：玩扑克牌或者打麻将时将新拿到的牌插入已经从大到小排好序的序列中，使其保持排序不变。

详细步骤对于一个要采用插入排序来排序的数组来说，首先要将数组分成前后两段，前边的是已经有序的数组，后边的是待排序的数组，将待排序数组的首个数字取出来，插入已经排好序的前段中合适位置即可。插入排序法的时间复杂度是O(n2)，但是相比冒泡排序和选择排序来说，性能更优，因为插入排序实际复杂度是n2/4，而冒泡和选择排序均是n2/2。

代码如下：

public static void insertSort(int [] nums) {
	 //从1开始是待排序数组，第0个元素肯定有序，因为前边只有一个元素
	 for(int i=1;i<nums.length;i++) {
		 int temp=nums[i];
		 int j; //初始化有序数组的下标
		 //当要插入的元素小于有序数组中的某些元素时，将这些元素往后挪一位
		 for(j=i-1;j>=0 && temp<nums[j]; j--) {
			 nums[j+1]=nums[j];
		 }
		 //当插入的元素大于或者等于有序数组中的元素时，将该位置的元素值设为插入元素的值
		 nums[j+1]=temp;
	 }
 }