집 >백엔드 개발 >PHP 튜토리얼 >PHP 정렬 알고리즘 Bubble Sort(버블 정렬)

PHP 정렬 알고리즘 Bubble Sort(버블 정렬)

不言원래의: 2018-04-20 13:05:461720검색

이 글에서는 주로 PHP 정렬 알고리즘의 Bubble Sort 구현 방법을 소개합니다. 이는 Dahua 데이터 구조의 알고리즘을 참조하고 Bubble Sort의 원리 및 관련 구현 기술에 대한 보다 자세한 분석과 예제를 결합한 것입니다. 다음을 참고하세요

본 글의 예시에서는 PHP 정렬 알고리즘 중 Bubble Sort(Bubble Sort)의 구현 방법을 설명하고 있습니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

기본 아이디어:

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

가장 간단한 정렬 구현:

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

//这里使用了类型提示（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);
      }
    }
  }
}

버블 정렬 알고리즘 개선:

"Dahua Data Structure"는 정말 좋은 책입니다. 우리에게 주세요. 버블 정렬 알고리즘의 개선 사항을 소개합니다. 여기서는 해당 내용을 직접 인용하겠습니다.

위의 버블 정렬 알고리즘이 여전히 최적화될 수 있나요? 대답은 '예'입니다. 우리가 정렬하려는 순서가 {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;
      }
    }
  }
}

코드 변경의 핵심은 태그 쌍을 추가하는 것입니다. 이러한 개선을 거쳐 플래그가 true인지 판단하는 버블 정렬 성능이 향상되어 순서가 이미 올바른 경우 의미 없는 루프 판단을 피할 수 있습니다.

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

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

이 기사는 "Dahua 데이터 구조"를 참조했습니다. 나중에 참고할 수 있도록 여기에만 기록했습니다.

PHP 정렬 알고리즘 Bubble Sort(버블 정렬)

관련 기사