1 算法描述
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤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 < arrs.length; i++) { System.out.print(arrs[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 < arrs.length; i++) { System.out.print(arrs[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 < arrs.length; i++) { System.out.print(arrs[i]+","); }
分解4：使用循环操作优化多轮的插入操作
int[] arrs = { 8, 6, 1, 7, 2, 5, 4, 12, 9 }; /// 第一轮插入 for (int start = 1; start < arrs.length; start++) { //获取未排序数组的第一个数组 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; } } ///输出结果 for (int i = 0; i < arrs.length; i++) { System.out.print(arrs[i]+","); }
插入排序的交换次数多，但是循环比较的次数少
