插入排序的这两种实现之间的区别

Question

我觉得这两个实现在做同样的事情，但如果您也能告诉我它们是否（在性能方面）在做同样的事情（例如，在执行的指令数方面），那就太好了。谢谢

<?php

$arr = array(10, 2, 3, 14, 16);

function sortOne($arr) {

    $instructionCount = 0;

    for ($i = 1; $i < count($arr); $i++) {
        $instructionCount++;
        for ($j = $i - 1; $j >= 0 && ($arr[$j] > $arr[$i]); $j--) {
            $instructionCount++;

            $tmp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $tmp;

        }
    }

    echo "\nTotal Instructions for Sort One: $instructionCount\n"; 

    return $arr;
}

function sortTwo($array) {

    $instructionCount = 0;

    for($j=1; $j < count($array); $j++){
        $instructionCount++;
        $temp = $array[$j];
        $i = $j;
        while(($i >= 1) && ($array[$i-1] > $temp)){
            $instructionCount++;
            $array[$i] = $array[$i-1];
            $i--;
        }
        $array[$i] = $temp;
    }

    echo "\nTotal Instructions for Sort Two: $instructionCount\n"; 

    return $array;
}


var_dump(sortOne($arr));

Answer 1

不，它们不一样。函数 sortOne 是 insertion sort 的错误实现 。

函数sortOne的正确实现是：

for ($i = 1; $i < count($arr); $i++) {
    $instructionCount++;
    $temp = $arr[$i];
    for ($j = $i - 1; $j >= 0 && ($arr[$j] > $temp); $j--) {
        $instructionCount++;
        $arr[$j + 1] = $arr[$j];                
    }
    $arr[$j + 1] = temp;
}

从现在的表现来看，他们的表现基本相当。只需将 for 循环更改为 while 循环，您将不会获得任何性能变化。

插入排序的这两种实现之间的区别

Difference between these two implementations of Insertion Sort

php

algorithm

sorting

insertion-sort