PHP 버블 정렬(Bubble Sort) 알고리즘에 대한 자세한 설명

머리말

버블 정렬은 대략 인접한 두 숫자를 순서대로 비교한 다음 마지막 두 자리까지 크기에 따라 정렬하는 것을 의미합니다. 정렬 과정에서는 항상 작은 숫자가 앞쪽에 배치되고 큰 숫자가 뒤쪽에 배치되는데, 이는 거품이 떠오르는 것과 동일하므로 이를 버블 정렬이라고 합니다. 하지만 실제로 실제 과정에서는 필요에 따라 역으로 사용할 수도 있습니다. 큰 나무는 앞으로 배치되고 소수는 뒤로 배치됩니다.

실제 전투

직접 코드:

<?php
/**
 * 冒泡排序算法示例
 */

// 这里以一维数组做演示
$demo_array = array(23,15,43,25,54,2,6,82,11,5,21,32,65);

// 第一层for循环可以理解为从数组中键为0开始循环到最后一个
for ($i=0;$i<count($demo_array);$i++) {
    // 第二层将从键为$i的地方循环到数组最后
    for ($j=$i+1;$j<count($demo_array);$j++) {
        // 比较数组中相邻两个值的大小
        if ($demo_array[$i] > $demo_array[$j]) {
            $tmp            = $demo_array[$i]; // 这里的tmp是临时变量
            $demo_array[$i] = $demo_array[$j]; // 第一次更换位置
            $demo_array[$j] = $tmp;            // 完成位置互换
        }
    }
}

// 打印结果集
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
var_dump($demo_array);
echo &#39;

';

실행 결과:

array(13) {
  [0]=>
  int(2)
  [1]=>
  int(5)
  [2]=>
  int(6)
  [3]=>
  int(11)
  [4]=>
  int(15)
  [5]=>
  int(21)
  [6]=>
  int(23)
  [7]=>
  int(25)
  [8]=>
  int(32)
  [9]=>
  int(43)
  [10]=>
  int(54)
  [11]=>
  int(65)
  [12]=>
  int(82)
}

위 결과에서 배열에 있는 것을 확인할 수 있습니다. 키 값 순서가 변경되어 정렬에 성공했습니다.

위 알고리즘이 배열의 키 값을 값 크기에 따라 작은 것부터 큰 것 순으로 정렬하는 것이라면, 역으로 큰 것에서 작은 것 순으로 연산하는 방법은 무엇일까요?

매우 간단합니다. 다음과 같이 비교 기호를 수정하면 됩니다.

<?php
/**
 * 冒泡排序算法示例
 */

// 这里以一维数组做演示
$demo_array = array(23,15,43,25,54,2,6,82,11,5,21,32,65);

// 第一层for循环可以理解为从数组中键为0开始循环到最后一个
for ($i=0;$i<count($demo_array);$i++) {
    // 第二层将从键为$i的地方循环到数组最后
    for ($j=$i+1;$j<count($demo_array);$j++) {
        // 比较数组中相邻两个值的大小
        if ($demo_array[$i] < $demo_array[$j]) {
            $tmp            = $demo_array[$i]; // 这里的tmp是临时变量
            $demo_array[$i] = $demo_array[$j]; // 第一次更换位置
            $demo_array[$j] = $tmp;            // 完成位置互换
        }
    }
}

// 打印结果集
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
var_dump($demo_array);
echo &#39;

';

실행 결과:

array(13) {
  [0]=>
  int(82)
  [1]=>
  int(65)
  [2]=>
  int(54)
  [3]=>
  int(43)
  [4]=>
  int(32)
  [5]=>
  int(25)
  [6]=>
  int(23)
  [7]=>
  int(21)
  [8]=>
  int(15)
  [9]=>
  int(11)
  [10]=>
  int(6)
  [11]=>
  int(5)
  [12]=>
  int(2)
}

그렇습니다. 순서는 쉽게 변경할 수 있습니다.

확장

위 코드를 자세히 살펴보면 주목할 만한 곳이 하나 있는데, 바로 변수 교환이 필요한 곳이다. 네, 이것도 버블링의 핵심 포인트입니다. 이 기술을 익히면 나중에 다른 곳에서도 사용할 수 있습니다.

여기서 이에 대해 조금 이야기해보겠습니다.

원리:

이제 두 개의 변수 A와 B가 있으며 요구 사항은 해당 값을 교환하는 것입니다.

질문을 보면 가장 먼저 직접 할당을 떠올릴 수 있지만, 직접 할당을 하게 되면 누가 누구에게 먼저 할당을 하든 그 중 하나는 반드시 덮어씌워진다는 것을 보면 알 수 있습니다. 세 번째 변수 C는 필요한 목표를 달성할 수 있도록 A 또는 B에 값을 임시로 저장합니다.

$c = $a; // 暂存
$a = $b; // b给a
$b = $c; // 暂存的a值再给b

참고: 실제로 세 번째 변수는 필요하지 않습니다. substr(), str_replace() 및 B 변수의 값을 교환하는 것도 가능합니다. 이는 버블 정렬을 도입하고 있기 때문에 너무 많은 확장입니다.

요약

버블 정렬에는 정말 많은 것들이 있습니다. 정리하자면, 두 가지 주요 사항이 있습니다:

루프 비교

키 값 교환

이 두 가지 사항을 완료할 수 있다면 기본적으로는 괜찮습니다. 물론 버블 정렬에는 많은 알고리즘이 있습니다. 관심 있는 학생들이 스스로 공부할 수 있습니다.