Jakesoft
V2EX  ›  PHP

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

  •  
  •   Jakesoft · Jun 20, 2016 · 5051 views
    This topic created in 3807 days ago, the information mentioned may be changed or developed.
    $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 replies  •  2016-06-21 16:29:41 +08:00
    Mirana
    Mirana
    Jun 20, 2016
    1
    冒泡啊。。。
    Jakesoft
    Jakesoft
    OP
    Jun 20, 2016
    2
    @Mirana 冒泡不是会在开始得到最大或者最小值吗?这个好像没有啊
    hxtheone
    hxtheone
    Jun 20, 2016
    3
    @Jakesoft 冒泡的最大值或最小值是在逐次交换中得到的吧? 开始得到最大或最小的不是堆排吗?
    ChiangDi
    ChiangDi
    Jun 20, 2016 via Android
    4
    插入排序吧,依次找到剩余的最大的插到前面,就跟打牌时那个插法一样。
    hinkal
    hinkal
    Jun 20, 2016
    5
    这是插入排序吧
    lechain
    lechain
    Jun 20, 2016 via Android
    6
    冒泡…鉴定完毕
    hinkal
    hinkal
    Jun 20, 2016
    7
    参见维基百科插入排序 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
    swuzjb
    Jun 20, 2016
    8
    标准的冒泡啊
    skydiver
    skydiver
    Jun 20, 2016 via iPad
    9
    明显是插入排序。冒泡只会交换相邻的。
    skydiver
    skydiver
    Jun 20, 2016 via iPad
    10
    不知道为什么这么多人认为是冒泡,难道是看到双层循环就说是冒泡?
    swuzjb
    swuzjb
    Jun 20, 2016
    11
    插入排序 冒泡的第二个循环 不是 0 到 i
    NightVermouth
    NightVermouth
    Jun 20, 2016
    12
    插入排序
    pupboss
    pupboss
    Jun 21, 2016 via iPhone
    13
    插入排序,在排列好的几个数里面,后面新的数只需要比最靠左边那个大,就可以插到他后面
    pupboss
    pupboss
    Jun 21, 2016 via iPhone
    14
    平时大家谈起算法,一个比一个看着牛逼,怎么遇到这种问题一个个的全都懵逼了
    best1a
    best1a
    Jun 21, 2016
    15
    少了个 break ,所以看起来比较古怪
    Jakesoft
    Jakesoft
    OP
    Jun 21, 2016
    16
    @pupboss 我用几个数画了一下发现这不是一个很好的排序,有些比较完全不必要,比如前面是 3 , 4 , 8 ,第四个数是 2 ,于是会用 2 (这个数就是 arr[3])跟前面的数都进行比较,如果比 2 大就交换位置,于是就是 2,4,8,3 ,然后还有两个交换,其实没必要,直接把 2 放在 3 的前面其实可以了,(我算法不是很熟,所以才敢发帖出来问各位)

    ps: 虽然发现不是很好的算法,但是感觉代码是不是最简单的...
    Jakesoft
    Jakesoft
    OP
    Jun 21, 2016
    17
    像是一个劣质的插入排序...
    hinkal
    hinkal
    Jun 21, 2016
    18
    @Jakesoft 你说的无用比较确实存在。但是这样代码简洁,适合用于表述插入排序的一般写法。
    best1a
    best1a
    Jun 21, 2016
    19
    - -啊,不对,不是少了个 break ,这东西是把大的往后挤,所以多了很多无用的比较
    LukeXuan
    LukeXuan
    Jun 21, 2016 via Android
    20
    插排…
    kingddc314
    kingddc314
    Jun 21, 2016 via Android
    21
    说是冒泡,却不是比较相邻元素
    说是插入,又是通过从前向后交换而不是从后向前插入
    所以这大概是冒插算法吧
    hinkal
    hinkal
    Jun 21, 2016
    22
    @Jakesoft 仔细看了下,这个并不是无用的比较,你想想,如果直接吧 3 , 4 , 8 这一段后移,你还得写一个带控制变量 i 的 for 循环, for 循环中 i 也需要比较啊!而且还会产生额外的临时变量。 https://gist.github.com/padeoe/9e04ab9550eb90daa7e46493e8888934
    upczww
    upczww
    Jun 21, 2016 via Smartisan T1
    23
    一大堆$,怪不得 PHP 是最好的语言,有钱
    Jakesoft
    Jakesoft
    OP
    Jun 21, 2016
    24
    @hinkal 嗯是的, a[j] = tmp;后面加一个 break;就好了,防止继续比较。哎,要睡觉了
    hinkal
    hinkal
    Jun 21, 2016
    25
    @Jakesoft 哎呀,忘记 break 了,已修改。也睡觉了
    hcwhan
    hcwhan
    Jun 21, 2016
    26
    bravecarrot
    bravecarrot
    Jun 21, 2016 via iPhone
    27
    插入排序嘛
    zjbztianya
    zjbztianya
    Jun 21, 2016
    28
    其实更像选择排序
    stormpeach
    stormpeach
    Jun 21, 2016
    29
    插入排序,始终维护的是一个有序的序列。

    把第一个循环的$i = 0 换成$i = 1,第二个循环的$j = 0 换成$j = $i - 1 就是冒泡排序
    hooluupog
    hooluupog
    Jun 21, 2016
    30
    这是插入排序。
    arr[0->j](j < i)是已经有序的子序列(升序);
    arr[i]是当前待排元素,和有序子序列依次比较寻找插入位置。
    fri3nds
    fri3nds
    Jun 21, 2016
    31
    @best1a 只是没有优化,没有利用已排好数据!交换次数比较多而已!
    Jakesoft
    Jakesoft
    OP
    Jun 21, 2016
    32
    可以结帖了,总结各位+自己的分析这是插入排序,插入排序的原理是维持一个排序的数列,然后 拿新的数字跟里面的逐一比较,网上找到的比较是从新数字的左临边向最左边比较,我的是总最左边开始比较,附上`常见的`插入排序:

    ```
    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
    Jakesoft
    OP
    Jun 21, 2016
    33
    @kingddc314 被你发现了,哈哈,不过这个原理来说应该算是插排
    lz3259
    lz3259
    Jun 21, 2016
    34
    @Jakesoft 加上一个 break 就完全不一样了
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   877 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 71ms · UTC 22:32 · PVG 06:32 · LAX 14:32 · JFK 17:32
    ♥ Do have faith in what you're doing.