请问如下排序到底是什么排序算法？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3070 天前的主题，其中的信息可能已经有所发展或是发生改变。

$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;
        }
    }
}

感觉不像冒泡排序：一开始就得到最大值或者最小值

也不像选择排序，身边找不到人解答，

就当破事水来一发咯。

arr

排序

len

temp

34 条回复 • 2016-06-21 16:29:41 +08:00

Mirana

2016-06-20 23:41:01 +08:00

冒泡啊。。。

Jakesoft

2016-06-20 23:44:16 +08:00

@Mirana 冒泡不是会在开始得到最大或者最小值吗？这个好像没有啊

hxtheone

2016-06-20 23:50:02 +08:00

@Jakesoft 冒泡的最大值或最小值是在逐次交换中得到的吧? 开始得到最大或最小的不是堆排吗?

ChiangDi

2016-06-20 23:52:13 +08:00 via Android

插入排序吧，依次找到剩余的最大的插到前面，就跟打牌时那个插法一样。

hinkal

2016-06-20 23:53:54 +08:00

这是插入排序吧

lechain

2016-06-20 23:55:18 +08:00 via Android

冒泡…鉴定完毕

hinkal

2016-06-20 23:56:13 +08:00

参见维基百科插入排序 java 实现的那一段和这个 php 写的代码结构一样
public static void insertion_sort( int[] arr ) {
for( int i=0; i<arr.length-1; i++ ) {
for( int j=i+1; j>0; j-- ) {
if( arr[j-1] <= arr[j] )
break;
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}

swuzjb

2016-06-20 23:56:17 +08:00

标准的冒泡啊

skydiver

2016-06-20 23:56:27 +08:00 via iPad

明显是插入排序。冒泡只会交换相邻的。

skydiver

2016-06-20 23:57:02 +08:00 via iPad

不知道为什么这么多人认为是冒泡，难道是看到双层循环就说是冒泡？

swuzjb

2016-06-20 23:57:54 +08:00

插入排序冒泡的第二个循环不是 0 到 i

NightVermouth

2016-06-20 23:58:44 +08:00

插入排序

pupboss

2016-06-21 00:06:29 +08:00 via iPhone

插入排序，在排列好的几个数里面，后面新的数只需要比最靠左边那个大，就可以插到他后面

pupboss

2016-06-21 00:10:03 +08:00 via iPhone

平时大家谈起算法，一个比一个看着牛逼，怎么遇到这种问题一个个的全都懵逼了

best1a

2016-06-21 00:14:20 +08:00

少了个 break ，所以看起来比较古怪

Jakesoft

2016-06-21 00:18:30 +08:00

@pupboss 我用几个数画了一下发现这不是一个很好的排序，有些比较完全不必要，比如前面是 3 ， 4 ， 8 ，第四个数是 2 ，于是会用 2 （这个数就是 arr[3]）跟前面的数都进行比较，如果比 2 大就交换位置，于是就是 2,4,8,3 ，然后还有两个交换，其实没必要，直接把 2 放在 3 的前面其实可以了，（我算法不是很熟，所以才敢发帖出来问各位）

ps: 虽然发现不是很好的算法，但是感觉代码是不是最简单的...

Jakesoft

2016-06-21 00:21:02 +08:00

像是一个劣质的插入排序...

hinkal

2016-06-21 00:23:06 +08:00

@Jakesoft 你说的无用比较确实存在。但是这样代码简洁，适合用于表述插入排序的一般写法。

best1a

2016-06-21 00:25:38 +08:00

- -啊，不对，不是少了个 break ，这东西是把大的往后挤，所以多了很多无用的比较

LukeXuan

2016-06-21 00:40:38 +08:00 via Android

插排…

kingddc314

2016-06-21 00:41:30 +08:00 via Android

说是冒泡，却不是比较相邻元素
说是插入，又是通过从前向后交换而不是从后向前插入
所以这大概是冒插算法吧

hinkal

2016-06-21 00:50:26 +08:00

@Jakesoft 仔细看了下，这个并不是无用的比较，你想想，如果直接吧 3 ， 4 ， 8 这一段后移，你还得写一个带控制变量 i 的 for 循环， for 循环中 i 也需要比较啊！而且还会产生额外的临时变量。 https://gist.github.com/padeoe/9e04ab9550eb90daa7e46493e8888934

upczww

2016-06-21 00:55:03 +08:00 via Smartisan T1

一大堆$，怪不得 PHP 是最好的语言，有钱

Jakesoft

2016-06-21 01:00:32 +08:00

@hinkal 嗯是的， a[j] = tmp;后面加一个 break;就好了，防止继续比较。哎，要睡觉了

hinkal

2016-06-21 01:05:51 +08:00

@Jakesoft 哎呀，忘记 break 了，已修改。也睡觉了

hcwhan

2016-06-21 01:18:47 +08:00

排序推荐看下这个 http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html

bravecarrot

2016-06-21 01:30:12 +08:00 via iPhone

插入排序嘛

zjbztianya

2016-06-21 10:01:52 +08:00

其实更像选择排序

stormpeach

2016-06-21 10:25:56 +08:00

插入排序，始终维护的是一个有序的序列。

把第一个循环的$i = 0 换成$i = 1,第二个循环的$j = 0 换成$j = $i - 1 就是冒泡排序

hooluupog

2016-06-21 11:31:15 +08:00

这是插入排序。
arr[0->j](j < i)是已经有序的子序列(升序)；
arr[i]是当前待排元素,和有序子序列依次比较寻找插入位置。

fri3nds

2016-06-21 11:57:51 +08:00

@best1a 只是没有优化，没有利用已排好数据！交换次数比较多而已！

Jakesoft

2016-06-21 12:31:36 +08:00

可以结帖了，总结各位+自己的分析这是插入排序，插入排序的原理是维持一个排序的数列，然后拿新的数字跟里面的逐一比较，网上找到的比较是从新数字的左临边向最左边比较，我的是总最左边开始比较，附上`常见的`插入排序：

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

Jakesoft

2016-06-21 12:33:18 +08:00

@kingddc314 被你发现了，哈哈，不过这个原理来说应该算是插排

lz3259

2016-06-21 16:29:41 +08:00

@Jakesoft 加上一个 break 就完全不一样了