집 >백엔드 개발 >PHP 튜토리얼 >버블링, 바이너리 삽입 및 빠른 정렬 알고리즘 소개

버블링, 바이너리 삽입 및 빠른 정렬 알고리즘 소개

jacklove원래의: 2018-06-11 09:47:502255검색

1. 버블 정렬 알고리즘
프로세스:
1. 전체 배열을 탐색하고 $a[$i]>$a[$i+1]과 같은 인접한 요소의 모든 쌍을 비교한 다음 위치를 바꿉니다. , 비교당 하나의 역순을 제거합니다.
2. 각 사이클이 끝나면 다음에 필요한 사이클 수가 1씩 줄어듭니다.

<?php
// 冒泡排序
$arr = createarr(20);
printarr($arr);
popsort($arr);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function popsort(&$arr){
    for($i=0,$length=count($arr)-1; $i<$length; $i++){
        for($j=0; $j<$length-$i; $j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }    
}
?>

2. 이진 삽입 정렬

프로세스:
1 먼저 원래 배열은 $low=0 $high=count($arr)-1입니다.
2. 삽입할 숫자를 배열의 중간 요소와 비교하세요.
가운데 요소보다 큰 경우 $low=$mid+1이 다음 판단을 위한 배열의 시작으로 사용됩니다.
가운데 요소보다 작을 경우 $high=$mid-1이 다음 판단을 위한 배열의 끝으로 사용됩니다.
3. $low>$high가 끝날 때까지 $low는 새 요소가 삽입되는 위치입니다.
4. 배열의 $low부터 시작하는 모든 요소를 하나씩 뒤로 이동한 다음 $low 위치에 새 요소를 삽입합니다.

<?php
// 二分法插入排序
$arr = createarr(20);
$key = mt_rand(0,99);
printarr($arr);
echo &#39;key=&#39;.$key.&#39;<br>&#39;;
binsort($arr, $key);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,99));
    }
    sort($arr); // 有序序列
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function binsort(&$arr, $key){
    $low = 0;
    $high = count($arr)-1;
    while($low<=$high){
        $m = $low + (int)(($high-$low)/2);
        $mkey = $arr[$m];
        if($key>=$mkey){
            $low = $m + 1;
        }else{
            $high = $m - 1;
        }
    }
    // 移动插入位置之后的元素,插入新元素
    for($i=count($arr)-1; $i>=$low; $i--){
        $arr[$i+1] = $arr[$i];
    }
    $arr[$low] = $key;
}
?>

3. 빠른 정렬
프로세스:
1. 일반적으로 배열의 첫 번째 요소를 키로 사용합니다.
2. length-1
3.j-- arr[j]4. i++ arr[i]>key인 경우 arr[i]와 arr[j ] 위치 교환
5. i==j가 완료될 때까지 3단계와 4단계를 반복합니다.
6. 키로 구분된 왼쪽 및 오른쪽 요소 집합에 대해 1, 2, 3, 4, 5(재귀적으로)를 실행합니다.

<?php
// 快速排序
$arr = createarr(20);
printarr($arr);
quicksort($arr, 0, count($arr)-1);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function quicksort(&$arr, $low, $high){
    if($low>=$high){
        return ;
    }
    $key = $arr[$low];
    $i = $low;
    $j = $high;
    $flag = 1;
    while($i!=$j){
        switch($flag){
            case 0:
                if($arr[$i]>$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 1;
                }else{
                    $i++;
                }
                break;
            case 1:
                if($arr[$j]<$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 0;
                }else{
                    $j--;
                }
                break;
        }
    }
    quicksort($arr, $low, $i-1);
    quicksort($arr, $i+1, $high);
}
?>

이 글에서는 버블링, 이분법 삽입, 빠른 정렬 알고리즘에 대해 설명합니다. 더 많은 관련 내용은 PHP 중국어 홈페이지를 참고해주세요.

버블링, 바이너리 삽입 및 빠른 정렬 알고리즘 소개

관련 기사