집 > 기사 > 백엔드 개발 > PHP 버블 정렬 사용에 대한 자세한 설명

PHP 버블 정렬 사용에 대한 자세한 설명

php中世界最好的语言원래의: 2018-05-16 15:20:273897검색

이번에는 PHP버블 정렬 사용법에 대해 자세히 설명하고, PHP 버블 정렬 사용 시 주의사항은 무엇인지 살펴보겠습니다.

기본 아이디어:

버블 정렬은 일종의 교환 정렬입니다. 기본 아이디어는 인접한 레코드의 키워드를 쌍으로 비교하고, 역순으로 되어 있으면 반대 레코드가 없을 때까지 교환하는 것입니다. 주문하다.

가장 간단한 정렬 구현:

다양한 정렬 방법을 배우기 전에 자주 사용되는 정렬 방법을 먼저 살펴보겠습니다(적어도 저는 그렇습니다...):

//这里使用了类型提示（type hint） array，不熟悉或者不习惯的同学大可去掉，不影响运算结果
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      //将小的关键字放前面
      if($arr[$i] > $arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);

위 코드 엄밀히 말하면, "인접한 레코드를 쌍으로 비교"하는 버블 정렬 아이디어를 만족하지 않기 때문에 표준 버블 정렬이 아닙니다. 아이디어는 단지 첫 번째 키워드부터 시작하여 각 키워드를 그 뒤에 오는 모든 키워드와 비교하고 교환하여 최소값을 얻는 것입니다. 하지만 이 알고리즘은 매우 비효율적이다.

버블 정렬 알고리즘:

정렬할 시퀀스를 반복적으로 방문하여 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다.

이 알고리즘의 이름은 정렬 후 배열의 더 큰 요소가 배열의 뒤쪽으로 점차적으로 "가라앉는" 반면, 작은 요소는 점차적으로 배열의 앞쪽으로 "떠다니는" 사실에서 유래된 이름입니다.

버블 정렬 알고리즘은 다음과 같이 작동합니다. (뒤에서 앞으로)

1. 인접한 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.
2. 처음의 첫 번째 쌍부터 끝의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.
3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
4.비교할 숫자 쌍이 더 이상 없을 때까지 매번 점점 더 적은 수의 요소에 대해 위 단계를 계속 반복합니다.

텍스트 설명으로는 이해가 안 되실 수도 있지만 코드를 보시면

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//冒泡排序
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    //从后往前逐层上浮小的元素
    for($j = $length - 2;$j >= $i;$j --){
      //两两比较相邻记录
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

버블 정렬 알고리즘 개선:

위의 버블 정렬 알고리즘이 여전히 최적화될 수 있나요? 대답은 '예'입니다. 우리가 정렬하려는 순서가 {2,1,3,4,5,6,7,8,9}인 경우, 즉 첫 번째와 두 번째 키워드를 제외하고 다른 모든 항목을 교환해야 한다고 상상해 보세요. . 이미 정상적인 순서입니다. i = 0, 2, 1이 교환되고 이때의 시퀀스는 이미 순서대로 되어 있지만 알고리즘은 데이터가 교환되지 않았음에도 불구하고 여전히 i = 2 ~ 9와 각 루프에서 j 루프를 실행합니다. 그러나 광범위한 비교 그 뒤의 내용은 대체로 중복되었습니다.
i = 2일 때, 우리는 이미 9와 8, 8과 7, ·······················3과 2를 데이터 교환 없이 비교했는데, 이는 이 순서가 이미 순서대로 되어 있으므로 후속 작업을 계속할 필요가 없음을 의미합니다. 판단 작업(다음 작업에서는 데이터 교환이 발생하지 않으며 다시 수행하는 것은 의미가 없습니다). 이 아이디어를 실현하려면 코드를 개선하고 이 알고리즘의 개선을 실현하기 위해 마크 변수 플래그를 추가해야 합니다.

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换，则整个数组已经是有序的了)
function BubbleSort1(array &$arr){
  $length = count($arr);
  $flag = TRUE;
  for($i = 0;($i < $length - 1) && $flag;$i ++){
    $flag = FALSE;
    for($j = $length - 2;$j >= $i;$j --){
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
        $flag = TRUE;
      }
    }
  }
}

코드 변경의 핵심은 for 루프에 플래그가 true인지 여부를 추가하는 것입니다. i 변수 판단의 이러한 개선 이후 버블 정렬의 성능이 일부 향상되어 순서가 이미 순서대로 되어 있을 때 의미 없는 루프 판단을 피할 수 있습니다.

버블 알고리즘의 총 시간 복잡도는 O(n^2)입니다.

버블 정렬은 안정적인 정렬입니다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!