php插入排序

sisophon 2019-10-01 PM 14℃ 0条

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。

原理:

a.从第一个元素开始,该元素可以认为已经被排序

b.取出下一个元素,在已经排序的元素序列中从后向前扫描

c.如果该元素(已排序)大于新元素,将该元素移到下一位置

d.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

e.将新元素插入到该位置后

f.重复步骤2~5

代码:

$arr = array(5,2,3,9,1);
$count = count($arr);
if ($count < 2) {
    return $arr;
}
for ($i = 1; $i < $count; $i++) {
    // 当前值
    $temp = $arr[$i];
    for ($k = $i - 1; $k >= 0; $k--) {
        // 条件成立,比较值后挪一位,将当前值替换成比较值
        // 倒序 $temp > $arr[$k]
        if ($temp < $arr[$k]) {
            $arr[$k + 1] = $arr[$k];
            $arr[$k] = $temp;
        }
    }
}

解析:

第一轮

第一次:

i k
1 0

$temp 等于$arr[$i] 即等于$arr[1]=2

$arr[$k] 等于$arr[0] 即等于5

因为2<5,所以置换以后结果是:2 5 3 9 1

第二轮

第一次:

i k
2 1

$temp 等于$arr[$i] 即等于$arr[2]=3

$arr[$k] 等于$arr[1] 即等于5

因为3<5,所以置换结果是:2 3 5 9 1

第二次:

i k
2 0

$temp 等于$arr[$i] 即等于$arr[2]=3

$arr[$k] 等于$arr[1] 即等于2

因为3>2,结果不变。

第三轮

第一次:

i k
3 2

$temp 等于$arr[$i] 即等于$arr[3]=9

$arr[$k] 等于$arr[2] 即等于5

因为9>5,结果不变。

第二次:

i k
3 1

$temp 等于$arr[$i] 即等于$arr[3]=9

$arr[$k] 等于$arr[1] 即等于3

因为9>3,结果不变。

第三次:

i k
3 0

$temp 等于$arr[$i] 即等于$arr[3]=9

$arr[$k] 等于$arr[0] 即等于2

因为9>2,结果不变。

第四轮

第一次:

i k
4 3

$temp 等于$arr[$i] 即等于$arr[4]=1

$arr[$k] 等于$arr[3] 即等于9

因为1<9,置换结果是:2 3 5 1 9

第二次:

i k
4 2

$temp 等于$arr[$i] 即等于$arr[4]=1

$arr[$k] 等于$arr[2] 即等于5

因为1<5,置换结果是:2 3 1 5 9

第三次:

i k
4 1

$temp 等于$arr[$i] 即等于$arr[4]=1

$arr[$k] 等于$arr[1] 即等于3

因为1<3,置换结果是:2 1 3 5 9

第四次:

i k
4 0

$temp 等于$arr[$i] 即等于$arr[4]=1

$arr[$k] 等于$arr[0] 即等于2

因为1<2,置换结果是:1 2 3 5 9

最终结果为:1 2 3 5 9

复杂度:

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需{displaystyle n-1}{displaystyle n-1}次即可。

最坏情况就是,序列是降序排列,那么此时需要进行的比较共有{displaystyle {frac {1}{2}}n(n-1)}{displaystyle {frac {1}{2}}n(n-1)}次。插入排序的赋值操作是比较操作的次数减去{displaystyle n-1}{displaystyle n-1}次,(因为{displaystyle n-1}{displaystyle n-1}次循环中,每一次循环的比较都比赋值多一个,多在最后那一次比较并不带来赋值)。平均来说插入排序算法复杂度为{displaystyle O(n^{2})}O(n^{2})。

因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千;或者若已知输入元素大致上按照顺序排列,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)

标签: PHP

非特殊说明,本博所有文章均为博主原创。

上一篇 php选择排序
下一篇 php快速排序

评论啦~