java关于插入排序的问题，我写出来了，输出结果是对的，但是我写注释的时候分析了下应该结果是错的。。。
发布网友
发布时间：2022-05-15 10:04
共3个回答
热心网友
时间：2023-10-19 15:14
首先从逻辑上看，楼主的插入排序跟原始的插入排序算法不太一样，但是达到了同样的目的。虽然计算次数没有像原始的插入优化的那么好。但是没有错误。
先说，楼主如果写成for(int j=i;j<i+1;j++) 这样铁定是错的。
你这样无论i为多少，这个循环只能运行一次。可以等价为for(int j=i;j<=i;j++) 。如果楼主希望j的初值是i的话，那么就写成for(int j=i;j>=0;j--)
第二，楼主说到第0个元素没有被比较，是错误的。
楼主的if中，判断的是array[i]与array[j-1]做比较。而外面for中j的范围是[1，i]，而if中是j-1，那么array[j-1]的范围就是[0，i-1]。所以0是被做了比较的。同样的道理，楼主注释中说“只和相邻的元素进行了比较”，也可以用上面的思路解释了。
随后说说算法优化问题。
这个似乎不属于楼主提问的范围，没兴趣的话请无视
常见的插入排序是这样的（摘自百度百科，词条：插入排序）
for(int i=1;i<arr.length;i++){for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
//TODO:
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
//接下来是无用功
break;
}
}
}
这里与楼主最大的不同就是它的j是倒叙，另外if之后有else和break
具体我们用{1，2，3，5，6，7，4}这个数组来看下。
当i<6时，楼主的代码，需要进行15次判断，而常见的只要进行5次。而在i=6时。原始的代码需要进行4次排序就可以完成任务，而楼主的需要进行6次。总数是21：9。
至于break减少的判断的作用我就不提了。问题在于j的正序与倒序。对于4这个数，实际上没有意义去比较3之前的数字了，但若是正序，则需要从头开始寻找，所以有无用功的比较次数存在。
如果这个数组比较特别，那我们换一个{4,5,1,8,2,9,3}，结果是21：14。看到运算次数的差距了么
说了半天，废话比较多，希望对楼主有帮助
追问小数据来说，冒泡排序和选择排序，哪个效率高，我刚才测试了一个小数据，冒泡，选择次数都是22，插入是7.两个相同的是巧合吗？从效率上来看，冒泡是比较每一个相邻位置，找出最大的放在最后面，并且越到后面，比较的次数越少，选择排序是选择最小的位置，其他每一个都与其比较，小的放进去，也是越往后越少，二者的区别在哪里？追答 http://blog.jobbole.com/68774/
这个是之前在CSDN上转载的一篇写得很好的排序算法效率的测试评估报告。这个网页我找了好久（毕竟时间有点长），推荐去看下。有一点需要注意的是，报告中的运行测试环境是php不是java。php本身属于服务器解释型语言，他本身有一个sort函数，采用服务器本身的硬件来完成排序，这个个效率是逻辑性排序算法不能比拟的；像java这种编译型的语言不具备类似sort这种函数。除此之外，对于逻辑型排序算法的运行效率java和php是没有什么区别的
先说小数据
就报告中，小数据（1000以内）下冒泡排序以及其变种，效率都非常的低。而相对于冒泡，选择的效率则要高很多。
其次是楼主做的那个测试。
有巧合出现相同情况的几率。还以我之前用那个{4,5,1,8,2,9,3}为例，选择排序，循环运算次数21次，交换5次。冒泡排序，循环18次，交换9次。对于计算机运算来讲，比较要比交换要来的快得多，所以相比较之下，选择的速度要快
最后说说区别
冒泡只能和相邻的数字进行比较，虽然规则比较简单易懂，但是盲目性比较高。如果最小值处于最后一位，那么第一次循环，就要进行数组长度-1次交换和判断。而选择似乎比冒泡的代码要复杂些，但是在刚才那个条件中，只需要进行数组长度-1次的判断和1次的交换。目的性比冒泡要强的多，虽然比较次数不会少于冒泡。
热心网友
时间：2023-10-19 15:14
for(int i=1;i<array.length;i++){
for(int j=1;j<i+1;j++){
if(array[j]<array[j-1]){
int temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
和之前比较不是for的问题， 是后面判断的问题， 你写的是if(array[i]<array[j-1])， 这个是不会一次性和之前的比较完的。 但如果if(array[j]<array[j-1])这样写， 不就是每次都比较了吗？
不知道我理解错你的意思没有追问用IF是不能完场插入排序的，后面要用while，插入排序还是很有意思的
追答我明白你的意思了 ， while可能死掉， 还是用for 。 但嵌套3层循环有点那个啥了， 程序可以改进 ..... 后续跟进
热心网友
时间：2023-10-19 15:15
你写得这个方法像冒泡排序却又不是冒泡排序
