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 $demo_array[$j]) {            $tmp            = $demo_array[$i]; // 这里的tmp是临时变量
            $demo_array[$i] = $demo_array[$j]; // 第一次更换位置
            $demo_array[$j] = $tmp;            // 完成位置互换
        }
    }
}// 打印结果集echo &#39;&#39;;
var_dump($demo_array);echo &#39;&#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;&#39;;
var_dump($demo_array);echo &#39;&#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)
}

끝입니다. 순서를 쉽게 변경하세요.

Extension

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

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

원리:

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

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

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

참고: 실제로 세 번째 변수는 필요 없으며 A와 B 변수의 값을 서로 바꿔 사용할 수 있습니다. (), str_replace() 등 메서드입니다. 여기서는 버블 정렬을 도입하므로 너무 많이 확장하지는 않겠습니다.

요약

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

• 루프 비교

• 키 값 교환

이 두 가지 사항을 모두 완료할 수 있다면 기본적으로는 괜찮습니다. 물론 버블 정렬에는 여러 가지 알고리즘이 있지만, 여기에만 나와 있습니다. 그 중 하나는 관심 있는 학생들이 스스로 연구를 할 수 있다는 것입니다.