算法题2 插序算法

首先分析插序算法的原理：
举例：int [] ints = {0,1,3,4,9,3,2,3,5,1,0};
for循环进行遍历，判断相邻两个值得大小，如果前面的小于后面的，就开始进行阶循环。
即9,3时，也就是i循环

for (int i = 1; i <= ints.length-1; i++) {if(ints[i]<ints[i-1]) {//此时进入阶循环 j}}

阶循环时，从0,1，。。。4,9，进行循环，判断其中j位上的值比i位上的值大的那一位。

for (int i = 1; i <= ints.length-1; i++) {if(ints[i]<ints[i-1]) {//此时进入阶循环 jif(ints[j]>ints[i]) {}}

这时需要找到介于阶循环中的j ，j 位的值比i位的值大。
需要交换的是j位于i位；j与i位之间的需要后移。先后移即i-1 移到i，直到j+1 移到j+2;最后交换j与i位。

for (int i = 1; i <= ints.length-1; i++) {if(ints[i]<ints[i-1]) {//当i位的值小于i-1位的值时，开始进行阶循环for (int j = 0; j <=i-1; j++) {//当j位的值大于i位的值时if(ints[j]>ints[i]) {int temp=ints[i];for (int k = i; k >=j; k--) {ints[k]=ints[k-1];}ints[j]=temp;}}}}

最后写成方法：

static int[] insertion(int[] ints) {for (int i = 1; i <= ints.length-1; i++) {if(ints[i]<ints[i-1]) {//当i位的值小于i-1位的值时，开始进行阶循环for (int j = 0; j <=i-1; j++) {//当j位的值大于i位的值时if(ints[j]>ints[i]) {int temp=ints[i];for (int k = i; k >=j; k--) {ints[k]=ints[k-1];}ints[j]=temp;}}}}return ints;}

还没有结束，检查方法中冗余的计算，发现可以中断一些后面没用的循环，不是i,也不是k,而是j.

static int[] insertion(int[] ints) {for (int i = 1; i <= ints.length-1; i++) {if(ints[i]<ints[i-1]) {//当i位的值小于i-1位的值时，开始进行阶循环for (int j = 0; j <=i-1; j++) {//当j位的值大于i位的值时if(ints[j]>ints[i]) {int temp=ints[i];for (int k = i; k >=j; k--) {ints[k]=ints[k-1];}ints[j]=temp;break;}}}}return ints;}

最后进一步优化，减少一步循环

static int[] insertion2(int[] ints) {for (int i = 1; i <= ints.length-1; i++) {for (int j = i; j >0; j--) {if(ints[j]<ints[j-1]) {int temp=ints[j-1];ints[j-1]=ints[j];ints[j]=temp;}}}return ints;}

总结

以上是生活随笔为你收集整理的算法题2 插序算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。