插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

插入排序，想一下以前在上课的时候，老师在给我们排队时，有没有这样的举动，让你和在你前面的同学，比身高，如果你比前面的同学矮的话，前面的同学就站到你的位置，然后你在和你现在前面的同学进行身高比较，如果你还是比较矮的话，前面的同学则换到你的位置。直到你比前面同学高为止，将你插入前面同学后面。

假设老师从第二个同学开始调整位置，然后一直调整到最后一位，那么这种排序的方法就叫做插入排序。

下面以五个无序数据为例：

3,1,5,4,2

第一次排序，1比3小，则1和3换位置，变为了1,3,5,4,2

第二次排序，5比3大，不需要调整，仍未1,3,5,4,2

第三次排序，4比5小，则4和5 换位置，此时4比3大，则不再继续调整，此时变为了1,3,4,5,2

第四次排序，2比5小，2和5换位置，2又比4小，2继续和4换位置，2仍然比3小，继续和3换位置，最后2比1大，不再调整。最终，变成了1,2,3,4,5.

数据变成了有序。

动图演示

001.gif

实例

1. 代码实现

public class InsertTest {
    public static void main(String[] args) {
        int[] sorts = {3,2,1,4,6,5,8,7,10,9};
        
        System.out.println("排序前：");
        
        print(sorts);
        
        insertSort(sorts);
        
        System.out.println("\n排序后：");
        print(sorts);
    }
    
    public static void insertSort(int[] arrs) {
        for (int i = 0;i < arrs.length;i++) {
            int j;
            int temp = arrs[i];
            
            for(j = i - 1;j >= 0 && arrs[j] > temp;j--) {
                arrs[j+1] = arrs[j];
            }
            
            arrs[j+1] = temp;
            
        } 
    } 
    
    public static void print(int[] arrs) {
        for(int i = 0;i<arrs.length;i++) {
            System.out.print(arrs[i] + " ");
        }
    }
}

2. 输出结果

   
   02.png