PHP는 6가지 정렬 알고리즘을 구현합니다.

1. 삽입 정렬

단어를 사용하여 간단히 설명합니다. 예: $arr = array(4,2,4,6,3,6,1,7,9); 이렇게 순차 정렬을 수행합니다:
그런 다음 먼저 배열의 두 번째 요소를 첫 번째 요소와 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 두 번째 요소의 위치를 ​​교환합니다. 첫 번째 요소가 있는 배열의 세 요소는 각각 두 번째 및 첫 번째 요소와 비교됩니다. 세 번째 요소가 더 작으면 서로 교체됩니다. 등. 이는 삽입 정렬이며 시간 빈도는 1+2+...+(n-1)=(n^2)/2입니다. 그러면 시간 복잡도는 O(n^2)입니다.

php 구현 코드는 다음과 같습니다.

Php 코드

<?php  
        function insertSort($arr){  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              for($i=1;$i<$count;$i++){  
                    $tmp = $arr[$i];  
                     $j=$i-1;  
                     while(j>=0&&$arr[$j]<$arr[$i]){  
                         $arr[$i] = $arr[$j];                        
                         $arr[$j] = $tmp;  
                         $j--;  
                     }  
               }  
               return $arr;   
         }  
?>

둘, 선택 정렬

선택 정렬을 언어로 설명하면 다음과 같이 될 수 있습니다. $arr = array(4,3,5,2,1)
먼저 첫 번째를 비교합니다. 하나는 다음의 모든 것과 함께 가장 작은 숫자를 찾은 다음 첫 번째 배열과 교환합니다(물론 첫 번째 배열이 가장 작으면 교환할 필요가 없습니다). 그런 다음 루프를 실행합니다. 즉, 다음을 비교합니다. 두 번째 숫자는 다음 숫자와 일치하고 가장 작은 숫자는 두 번째 숫자로 바뀌는 식으로 계속 진행됩니다. 이는 매번 가장 작은 남은 값이 발견됨을 의미합니다. 얻을 수 있습니다: 처음에는 시간 빈도가 n입니다. (첫 번째는 다음 n-1과 비교하여 가장 작은 것을 찾은 다음 첫 번째인지 확인하고 그렇지 않으면 교환합니다.) future , 마이너스 1이 뒤따릅니다. 시간 복잡도도 O(n^2)입니다.

php 구현 코드는 다음과 같습니다.

Php 코드

<?php  
        function selectSort($arr){  
  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              for($i=0;$i<$count;$i++){  
                     $min=$i;  
                     for(j=$i+1;$j<$count;$j++){  
                         if($arr[$min]>$arr[$j]){  
                              $min = $j; //找到最小的那个元素的下标  
                         }  
                     }  
                     if($min!=$i){//如果下标不是$i 则互换。  
                            $tmp= $arr[$i];                        
                             $arr[$i] = $arr[$min];  
                             $arr[$min] = $tmp;  
                       }  
               }  
               return $arr;   
         }  
?>

세, 버블 정렬

버블 정렬은 실제로 선택 정렬과 크게 다르지 않습니다. 가장 작은 것을 찾아 가장 왼쪽에 놓습니다. 문제를 순서대로 풀어보세요. 차이점은 버블 정렬은 위치를 더 많이 바꾸는 반면 선택 정렬은 가장 작은 요소의 첨자를 찾은 다음 가장 왼쪽 요소와 위치를 직접 바꾸는 것입니다.
PHP 구현 코드는 다음과 같습니다.

PHP 코드

<?php  
        function selectSort($arr){  
  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              for($i=0;$i<$count;$i++){  
                     for(j=$i+1;$j<$count;$j++){  
                         if($arr[$i]>$arr[$j]){  
                              $tmp= $arr[$i];                        
                             $arr[$i] = $arr[$i];  
                             $arr[$i] = $tmp;  
                         }  
                     }  
               }  
               return $arr;   
         }  
?>

넷, 퀵 정렬

퀵 정렬, 언어로 표현하면, 배열에서 $a 값을 선택한 후 다른 요소와 비교하여 $a보다 크면 오른쪽 배열에 넣고, 그 반대의 경우 왼쪽 배열에 넣습니다. 그런 다음 각각 왼쪽과 오른쪽을 재귀적으로 호출합니다. 즉, 왼쪽과 오른쪽을 세분화하고 마지막으로 배열을 병합합니다.

php는 빠른 정렬을 구현합니다:

Php 코드

<?php  
        function mySort($arr){  
  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              $key = $arr[0];//选择第一个元素作为比较元素，可选其他  
               $left = array();                
               $right = array();  
               for($i=1;$i<$count;$i++){  
                     if($key>=$arr[$i]){  
                         $left[] = $arr[$i];    
                     }else{  
                          $right[] = $arr[$i];  
                      }  
               }  
               $left = mySort($left);  
               $right = mySort($right);  
               $result = array_merge($left,$right);  
               return $result;   
         }  
?>

5. 병합 정렬
사실 병합 정렬은 분할의 아이디어입니다. 그리고 병합. 왼쪽에 하나의 더미, 오른쪽에 하나의 더미를 만든 다음 병합하는 퀵 정렬이라는 아이디어와 공통점이 있습니다. 정렬은 재귀를 통해 이루어집니다. 차이점은 무엇입니까? 그 차이는 생각의 본질적인 차이이기도 합니다. 퀵 정렬의 분할은 크기 비교를 위해 특정 값을 선택하여 왼쪽과 오른쪽으로 나눕니다. 즉, 작은 더미는 왼쪽에 배치되고, 큰 더미는 오른쪽에 배치됩니다. 그런 다음 작은 왼쪽이 left1과 right1로 세분화됩니다. . . . 정렬은 유사한 재귀를 수행하여 수행됩니다. 즉, 계속 세분화하면 재귀 마지막의 left1 이 최소값이 됩니다.

병합 정렬은 왼쪽과 오른쪽의 배열을 기하학적으로 2 또는 1의 최소 단위로 반복적으로 나눈 다음 크기를 비교한 후 병합하는 것입니다. 여기서 비교 크기는 다음과 같습니다. 아들의 왼쪽 요소를 아들의 오른쪽 요소와 비교한 후 정렬하여 아버지의 왼쪽 또는 오른쪽으로 병합합니다. 여기서 마지막 두 배열을 각각 정렬하여 병합할 때까지 초기 왼쪽과 오른쪽은 각각의 순서만 확인할 수 없으며 전체 배열의 순서는 최종 왼쪽과 오른쪽을 통해서도 확인할 수 없습니다. 올바른 비교.

PHP 코드

<?php  
function gbSort($arr){  
       if(count($arr)<=1){return $arr;}  
       $min = floor(count($arr)/2);//取中间数字进行拆分  
       $left = array_slice($arr,0,$min);  
       $right = array_slice($arr,$min);  
       $left = gbSort($left);  //递归  
       $right = gbSort($right);  
       return get_merge($left,$right);//调用排序合并函数进行合并  
}  
function get_merge($left,$right){  
        while(count($left) && count($right)){  
               $m[] = $left[0]>$right[0] ? array_shift($right) : array_shift($left);  
               //进行比较，小的移除，并且放入到数组$m中。  
        }  
        return arr_merge($m,$left,$right);//进行合并（由于不知道left right 哪个会为空，所以进行统一合并）  
}  
  
?>

6. 힙 정렬
계속