插入排序算法简单笔记

插入排序的基本思想是：将第一个记录看成是有序序列，其余记录看成是无序序列。每次将无序序列中的一个记录按其关键字大小插入到已有序的序列中，直到全部记录插入为止。

具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5；

Java代码实现

public void InsertSort(){
        for(int index = 1; index<length; index++){/
            int temp = array[index];
            int leftindex = index-1;
            while(leftindex>=0 && array[leftindex]>temp){
                array[leftindex+1] = array[leftindex];
                leftindex--;
            }
            array[leftindex+1] = temp;
        }
    }

直接插入排序算法从空间来看，只需一个记录的辅助空间。从时间来看，该算法的基本操作是“比较两个关键字的大小和移动记录”，而比较的次数和移动记录的次数取决于待排序列的初始状态。

1. 最好情况下，初始关键字序列按非递减有序排列，每趟只需一次比较，总比较次数=n-1，总移动次数=2(n-1)次。
2. 最坏情况下，初始序列非递增有序排列时，对第j趟排序，插入记录需要同前面的j个记录进行j次比较，移动记录次数为j+2次。 总比较次数为             总移动次数为       
3. 在随机情况下，所需进行关键字的比较次数和移动次数约为n^2/4，综上所述，直接插入排序的时间复杂度为O(n^2)，是一个稳定的排序方法。