8
回答
请问这是什么排序算法?
【腾讯云】校园拼团福利,1核2G服务器10元/月!>>>   
$len = count($arr);

for ($i = 0; $i < $len; $i++) {
    for ($j = 0; $j < $i; $j++) {
        if ($arr[$i] < $arr[$j]) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }

}


为什么我感觉不像是冒泡排序?

举报
彩虹糖tang
发帖于2年前 8回/461阅
共有8个答案 最后回答: 2年前

这个是 插入排序

在每次外层循环开始前,A[0...$i]包含了原来的A[0...$i]的元素,并且已排序,直至$i=$len-1外层循环结束

内层循环是用来将新加入A[0...$i-1]数组中的A[$i]号元素与其他元素进行比较排序,保持升序排列用的

--- 共有 13 条评论 ---
前世疯狂回复 @彩虹糖tang : 我在下面贴上了优化后的代码,希望描述清楚了 2年前 回复
前世疯狂回复 @彩虹糖tang : 之前回复得匆忙了,上面给出的插入排序代码其实不是最优的体现,固定了尝试的次数为n(n-1)/2。其实优化后的插入排序尝试次数是会根据待排序的数组中逆序的个数而变化的,其比较方式为内层循环从后向前进行查询来查找第i个元素存放的位置,而不是从第一个元素开始。 2年前 回复
彩虹糖tang回复 @前世疯狂 : if不满足时不能break跳出来,比如: 2 4 8 3,这个数列,3会依次跟2 4 8 比较,发现 3比2大,不满足要求,此时如果break,就不能继续跟后面的4 8 比较了,所以不能break。 2年前 回复
前世疯狂回复 @Ambitor : 额,是的,表述有问题 2年前 回复
Ambitor@前世疯狂 额,应该是break哦? 2年前 回复
这个算法不是选择排序,选择排序的时间复杂度为O(n^2) 比较n^2次,但只交换N次,但是这个题目交换了N^2次,再来说它是不是插入排序,插入排序的复杂度为O(n)->O(n^2) 最好的比较次数为O(n),而这个算法他的比较次数是恒定的N^2次,理论上$i之前都是排好序的,所以应该$j交换后比较与他后面的数如果小于,那么之后的数也就不用再比较,而这个算法他的比较次数和冒泡一样是恒定的N^2,现在你应该知道它是不是冒泡了?感觉就是一个反向的冒泡排序
--- 共有 7 条评论 ---
Ambitor回复 @彩虹糖tang : 的确,如果用这种定义来说 不能说成冒泡,但我想说的是 算法优劣来讲的话 是研究他的时间复杂度和空间复杂度,对于它叫啥名字 我觉得无所谓-。-哈哈 2年前 回复
彩虹糖tang回复 @Ambitor : 我感觉不能说是冒泡排序,1,冒泡排序是比较相邻两个数,2:每一轮排序可以得到最大或者最小的数字,上面的这个在任何时候都没有确定最大和最小数,只是维持了一个排好序的数列 2年前 回复
Ambitor回复 @彩虹糖tang : 但是插入排序和上面的算法有个很重要的区别就是 如果当前这个数小于后面这个数 就不会再比较下一个了 因为这一段是已经排好序的。而这个算法 比较次数永远是n^2次。所以它是一个反向冒泡的排序过程 。。 2年前 回复
彩虹糖tang回复 @Ambitor : 如果按照插入排序打牌的方式(手里的牌都是排好序的,新牌会插入到合适位置),这样来说上面这个就是插入排序吧 2年前 回复
彩虹糖tang回复 @Ambitor : 好吧,我理解错了 2年前 回复
楼主可以自己把这个算法用一个很简单的数组测试下,依次用顺序、倒序测试,结果是他的比较次数是恒定不变的n(n-1)/2 也就是n^2  而插入排序的复杂度 比较次数是不恒定的。哈哈  参考这篇博文 http://blog.jobbole.com/79288/ 
--- 共有 2 条评论 ---
Ambitor回复 @彩虹糖tang : 哈哈 那就把标准答案改下吧,我刚抽时间谢了一篇关于这个的博客,哈哈 http://my.oschina.net/ambitor/blog/698525 可以加我微信交个朋友 2年前 回复
彩虹糖tang恩!你说的对,比较次数应该是这样子! 2年前 回复

第一层for循环控制冒泡的轮数,第二层for循环控制冒泡。

这么多明显的特征表名了这不就是冒泡排序么。。还什么选择排序、插入排序。


引用来自“前世疯狂”的评论

这个是 插入排序

在每次外层循环开始前,A[0...$i]包含了原来的A[0...$i]的元素,并且已排序,直至$i=$len-1外层循环结束

内层循环是用来将新加入A[0...$i-1]数组中的A[$i]号元素与其他元素进行比较排序,保持升序排列用的

$len = count($arr);

if($len > 1) {
    for($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
	for($j = i - 1; $j >= 0; $j--) {
	    if ($temp < $arr[$j]) {
	        $arr[$j + 1] = $arr[$j];
	        $arr[$j] = $temp;
	    }else {
	        $arr[$j + 1] = $temp;
	        break;
	    }
	}
    }
}



以上是优化后的插入排序代码

顶部