排序3-插入

1. 动图演示

2. 算法说明:  

    通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。   (有点像打扑克牌，抓牌的场景)

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

3. java源码实现

public static int[] insertSort(int[] sourceArray)  {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
}

      二.采用递归实现:

 public static void main(String[] args) {
        int [] x=new int[]{5,2,3,7,1,2,6,100,1};
        show( x );
        System.out.println();
        insertSort(  x,0,x.length-1);
        show(  x);
    }

public static void insertSort( int[] sourceArray, int first,int last){
        if(first<last){
            insertSort( sourceArray, first,last-1);
            insertInOrder(sourceArray[last],sourceArray,first,last-1);
        }
 }

private static void insertInOrder(int anEntry, int[] a, int begin, int end) {
        if( anEntry>=a[end]){
            a[end+1]=anEntry;
        }else if( begin<end) {
            a[end + 1] = a[end];
            insertInOrder(anEntry, a, begin, end - 1);
        }else{
            a[end+1]=a[end];
            a[end]=anEntry;
        }
}