排序算法之插入排序

1 算法描述

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

2 算法实现

分解1：从未排序数组中取出第一个元素，和已排序的集合中的元素进行比较，则将被比较的元素向后移动.直到数组的头部或者找到比前面的比取出的元素要小的位置。

  int[] arrs = { 8, 6, 1, 7, 2, 5, 4, 12, 9 };
      //获取未排序数组的第一个数组
      int insert  = arrs[1];
      //判断大小
      if(arrs[0]>insert) {
          //如果大则向后移动
          arrs[1] = arrs[0];
      }
      //找到出入的位置进行插入
      arrs[0] = insert;
      ///输出结果
      for (int i = 0; i  
分解2：重复分解1的操作,逐步扩展已排序好队列。
 
int[] arrs = { 8, 6, 1, 7, 2, 5, 4, 12, 9 };
      ///
      第一轮插入
      //获取未排序数组的第一个数组
      int insert  = arrs[1];
      //判断大小
      if(arrs[0]>insert) {
          //如果大则向后移动
          arrs[1] = arrs[0];
      }
      //找到出入的位置进行插入
      arrs[0] = insert;
      // 6, 8, 1, 7, 2, 5, 4, 12, 9
      ///
      第二轮插入
      insert  = arrs[2];
      //判断大小
      if(arrs[1]>insert) {
          //如果大则向后移动
          arrs[2] = arrs[1];
          //      1
          // 6, 8, 8 , 7, 2, 5, 4, 12, 9
      }
      if(arrs[0]>insert) {
          //如果大则向后移动
          arrs[1] = arrs[0];
          // 1      
          // 6, 6, 8 , 7, 2, 5, 4, 12, 9
      }
      // 1, 6, 8 , 7, 2, 5, 4, 12, 9
      //找到出入的位置进行插入
      arrs[0] = insert;
      ///
      ///第三轮插入
      insert  = arrs[3];
      //判断大小
      if(arrs[2]>insert) {
          //如果大则向后移动
          arrs[3] = arrs[2];
          //       7
          // 1, 6, 8 , 8, 2, 5, 4, 12, 9
      }
      if(arrs[1]>insert) {
          //如果大则向后移动
          arrs[2] = arrs[1];
      }else {
          //如果遇到前面的数字比插入的元素小，直接插入
          arrs[2] = insert;
          // 1, 6, 7 , 8, 2, 5, 4, 12, 9
      }
      ///输出结果
      for (int i = 0; i  
分解3：使用循环操作优化每一轮寻找插入位置的操作
（图片来源网络，侵删）
 
int[] arrs = { 8, 6, 1, 7, 2, 5, 4, 12, 9 };
        ///
        第一轮插入
        int start = 1;
        //获取未排序数组的第一个数组
        int insert  = arrs[start];
        while(start>0) {
            //判断大小
            if(arrs[start-1]>insert) {
                //如果大则向后移动
                arrs[start] = arrs[start-1];
            }else {
                //如果小于insert的话，就是插入的位置
                arrs[start] = insert;
                break; //循环中止
            }
            start --;
        }
        if(start==0) {
            arrs[0] = insert;
        }
        // 6, 8, 1, 7, 2, 5, 4, 12, 9
        ///
        第二轮插入
        start = 2;
        insert  = arrs[start];
        while(start>0) {
            //判断大小
            if(arrs[start-1]>insert) {
                //如果大则向后移动
                arrs[start] = arrs[start-1];
            }else {
                //如果小于insert的话，就是插入的位置
                arrs[start] = insert;
                break; //循环中止
            }
            start --;
        }
        if(start==0) {
            arrs[0] = insert;
        }
        ///
        ///第三轮插入
        start = 3;
        insert  = arrs[start];
        while(start>0) {
            //判断大小
            if(arrs[start-1]>insert) {
                //如果大则向后移动
                arrs[start] = arrs[start-1];
            }else {
                //如果小于insert的话，就是插入的位置
                arrs[start] = insert;
                break; //循环中止
            }
            start --;
        }
        if(start==0) {
            arrs[0] = insert;
        }
        ///输出结果
        for (int i = 0; i  
分解4：使用循环操作优化多轮的插入操作
 
 int[] arrs = { 8, 6, 1, 7, 2, 5, 4, 12, 9 };
        ///
        第一轮插入
        for (int start = 1; start 0) {
                //判断大小
                if(arrs[start-1]>insert) {
                    //如果大则向后移动
                    arrs[start] = arrs[start-1];
                }else {
                    //如果小于insert的话，就是插入的位置
                    arrs[start] = insert;
                    break; //循环中止
                }
                start --;
            }
            //如果是首位置，就直接插入
            if(start==0) {
                arrs[0] = insert;
            }
        }
        ///输出结果
        for (int i = 0; i  
插入排序的交换次数多，但是循环比较的次数少