Implémentation d'apprentissage PHP du tri par insertion

Le contenu principal de cet article est d'utiliser PHP pour implémenter le tri par insertion. C'est une question d'algorithme simple mais classique. Je me demande si vous vous en souvenez.

Idée de base du tri par insertion : Divisez le tableau en deux zones (zone triée et zone non triée). Supposons que le premier élément du tableau se trouve dans la zone triée, et le). premier élément Tous les éléments suivants se trouvent dans la section non triée. Une boucle double couche est utilisée lors du tri. La boucle externe est utilisée pour retirer les éléments à trier de la partie non triée et réduire progressivement la partie non triée. La boucle interne est utilisée pour trouver la position d'insertion de la partie triée (c'est-à-dire celle-ci). (c'est-à-dire en continu à partir de la partie triée). Recherchez les éléments plus grands que les éléments à trier), puis déplacez les éléments de la plus grande zone triée vers l'arrière. Le résultat final du mouvement vers l'arrière est que le dernier élément du tri. l'élément de zone occupe la position d'origine de l'élément à trier, et le milieu de la zone triée est vide d'une position), et enfin insérez l'élément à trier dans l'espace vide laissé après le déplacement de l'élément.

//插入排序
function insert_sort($arr) {
    //获取数组单元个数
    $count = count($arr);
    //外层循环用于从未排序区域中取出待排序元素
    for ($i=1; $i < $count; $i++) {
        //获取当前需要插入已排序区域的元素值
        $temp = $arr[$i];
        //内层循环用于从已排序区域寻找待排序元素的插入位置
        for ($j=$i-1; $j >= 0; $j--) {
            //如果$arr[$i]比已排序区域的$arr[$j]小，就后移$arr[$j]
            if ($temp < $arr[$j]) {        
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $temp;
            } else {
                //如果$arr[$i]不小于$arr[$j]，则对已排序区无需再排序
                break;
            }
        }
    }
    return $arr;
}

$arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
var_dump(insert_sort($arr));
　　测试结果：

　

Tutoriels associés : Tutoriel vidéo PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!