2018-04-09 插入排序

public void Isort(int[] number) {
    int n = number.length;
    int temp, i ,j;
    for(i = 1; i< n; i++) {
        temp = number[i];
        for(j = i; j>0 && number[j-1] > temp; j--) {
            number[j] = number[j-1];
        }
        number[j] = temp;
    }
}

java实现的插入排序，很简单，第一层循环是从左向右，第二层循环的初始值请注意，是i，而且有个判断条件就是j>0 && number[j-1] > temp，这样的话意味着第二层循环实际上就是从后往前，从i开始向0（循环开头）倒着遍历，这样第二层循环其实就是遍历当前下标i到数据源开头的位置，这样，如果数据源具备一定序列的话时间复杂度就是O（N）。最坏情况是O(n^2)。
网上还有一段有关插入和冒泡的比较，摘录于此：
这三种排序的思想

冒泡排序：在首轮，第一项和第二项比较，将大的放在后面，然后比较第二项和第三项，将大的放在后面，以此类推在首轮结束，最大的数据已经在最后一项了。在一轮轮的比较中，后面的已经排好的数据项越来越多，需要排序的数据项越来越少，直到为零。

选择排序：在冒泡排序上做了优化，减少了交换次数，在首轮选择最小的数放在第一项，一轮之后第一项是有序的了，第二轮从第二项开始选择最小的数放在第二项，以此类推，直到整个数组完全有序。

插入排序：和前俩种排序不同，插入排序在排序过程中是局部有序，随着插入项的增多，有序部分的项的位置会发生改变，而冒泡排序和选择排序每轮确定的项数的位置是永远不变的。在首轮，选择第二项作为插入项，然后取出这一项放在一个变量中，和前一项比较而且小，则前一项后移到第二项的位置，然后第二项也就是插入项放在前一项的位置，第二轮选择第三项作为插入项然后取出和前一项也就是第二项比较如果小，第二项后移到插入项，然后插入相在和第一项比较如果小，则第一项后移到第二项，插入项放在第一项，以此类推。