V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Jakesoft
V2EX  ›  PHP

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

  •  
  •   Jakesoft · 2016-06-20 23:32:19 +08:00 · 3742 次点击
    这是一个创建于 3059 天前的主题,其中的信息可能已经有所发展或是发生改变。
    $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;
            }
        }
    }
    

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

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

    就当破事水来一发咯。

    34 条回复    2016-06-21 16:29:41 +08:00
    Mirana
        1
    Mirana  
       2016-06-20 23:41:01 +08:00
    冒泡啊。。。
    Jakesoft
        2
    Jakesoft  
    OP
       2016-06-20 23:44:16 +08:00
    @Mirana 冒泡不是会在开始得到最大或者最小值吗?这个好像没有啊
    hxtheone
        3
    hxtheone  
       2016-06-20 23:50:02 +08:00
    @Jakesoft 冒泡的最大值或最小值是在逐次交换中得到的吧? 开始得到最大或最小的不是堆排吗?
    ChiangDi
        4
    ChiangDi  
       2016-06-20 23:52:13 +08:00 via Android
    插入排序吧,依次找到剩余的最大的插到前面,就跟打牌时那个插法一样。
    hinkal
        5
    hinkal  
       2016-06-20 23:53:54 +08:00
    这是插入排序吧
    lechain
        6
    lechain  
       2016-06-20 23:55:18 +08:00 via Android
    冒泡…鉴定完毕
    hinkal
        7
    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
        8
    swuzjb  
       2016-06-20 23:56:17 +08:00
    标准的冒泡啊
    skydiver
        9
    skydiver  
       2016-06-20 23:56:27 +08:00 via iPad
    明显是插入排序。冒泡只会交换相邻的。
    skydiver
        10
    skydiver  
       2016-06-20 23:57:02 +08:00 via iPad
    不知道为什么这么多人认为是冒泡,难道是看到双层循环就说是冒泡?
    swuzjb
        11
    swuzjb  
       2016-06-20 23:57:54 +08:00
    插入排序 冒泡的第二个循环 不是 0 到 i
    NightVermouth
        12
    NightVermouth  
       2016-06-20 23:58:44 +08:00
    插入排序
    pupboss
        13
    pupboss  
       2016-06-21 00:06:29 +08:00 via iPhone
    插入排序,在排列好的几个数里面,后面新的数只需要比最靠左边那个大,就可以插到他后面
    pupboss
        14
    pupboss  
       2016-06-21 00:10:03 +08:00 via iPhone
    平时大家谈起算法,一个比一个看着牛逼,怎么遇到这种问题一个个的全都懵逼了
    best1a
        15
    best1a  
       2016-06-21 00:14:20 +08:00
    少了个 break ,所以看起来比较古怪
    Jakesoft
        16
    Jakesoft  
    OP
       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
        17
    Jakesoft  
    OP
       2016-06-21 00:21:02 +08:00
    像是一个劣质的插入排序...
    hinkal
        18
    hinkal  
       2016-06-21 00:23:06 +08:00
    @Jakesoft 你说的无用比较确实存在。但是这样代码简洁,适合用于表述插入排序的一般写法。
    best1a
        19
    best1a  
       2016-06-21 00:25:38 +08:00
    - -啊,不对,不是少了个 break ,这东西是把大的往后挤,所以多了很多无用的比较
    LukeXuan
        20
    LukeXuan  
       2016-06-21 00:40:38 +08:00 via Android
    插排…
    kingddc314
        21
    kingddc314  
       2016-06-21 00:41:30 +08:00 via Android
    说是冒泡,却不是比较相邻元素
    说是插入,又是通过从前向后交换而不是从后向前插入
    所以这大概是冒插算法吧
    hinkal
        22
    hinkal  
       2016-06-21 00:50:26 +08:00
    @Jakesoft 仔细看了下,这个并不是无用的比较,你想想,如果直接吧 3 , 4 , 8 这一段后移,你还得写一个带控制变量 i 的 for 循环, for 循环中 i 也需要比较啊!而且还会产生额外的临时变量。 https://gist.github.com/padeoe/9e04ab9550eb90daa7e46493e8888934
    upczww
        23
    upczww  
       2016-06-21 00:55:03 +08:00 via Smartisan T1
    一大堆$,怪不得 PHP 是最好的语言,有钱
    Jakesoft
        24
    Jakesoft  
    OP
       2016-06-21 01:00:32 +08:00
    @hinkal 嗯是的, a[j] = tmp;后面加一个 break;就好了,防止继续比较。哎,要睡觉了
    hinkal
        25
    hinkal  
       2016-06-21 01:05:51 +08:00
    @Jakesoft 哎呀,忘记 break 了,已修改。也睡觉了
    hcwhan
        26
    hcwhan  
       2016-06-21 01:18:47 +08:00
    bravecarrot
        27
    bravecarrot  
       2016-06-21 01:30:12 +08:00 via iPhone
    插入排序嘛
    zjbztianya
        28
    zjbztianya  
       2016-06-21 10:01:52 +08:00
    其实更像选择排序
    stormpeach
        29
    stormpeach  
       2016-06-21 10:25:56 +08:00
    插入排序,始终维护的是一个有序的序列。

    把第一个循环的$i = 0 换成$i = 1,第二个循环的$j = 0 换成$j = $i - 1 就是冒泡排序
    hooluupog
        30
    hooluupog  
       2016-06-21 11:31:15 +08:00
    这是插入排序。
    arr[0->j](j < i)是已经有序的子序列(升序);
    arr[i]是当前待排元素,和有序子序列依次比较寻找插入位置。
    fri3nds
        31
    fri3nds  
       2016-06-21 11:57:51 +08:00
    @best1a 只是没有优化,没有利用已排好数据!交换次数比较多而已!
    Jakesoft
        32
    Jakesoft  
    OP
       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
        33
    Jakesoft  
    OP
       2016-06-21 12:33:18 +08:00
    @kingddc314 被你发现了,哈哈,不过这个原理来说应该算是插排
    lz3259
        34
    lz3259  
       2016-06-21 16:29:41 +08:00
    @Jakesoft 加上一个 break 就完全不一样了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5487 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 40ms · UTC 03:45 · PVG 11:45 · LAX 19:45 · JFK 22:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.