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
        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; 
         }
?>

2. 선택 정렬

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

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; 
         }
?>

3. 버블 정렬
버블 정렬은 실제로는 선택이 없습니다. 순위 차이가 심함. 가장 작은 것을 찾아 가장 왼쪽에 놓습니다. 문제를 순서대로 풀어보세요. 차이점은 버블 정렬은 위치를 더 많이 바꾸는 반면 선택 정렬은 가장 작은 요소의 첨자를 찾은 다음 가장 왼쪽 요소와 위치를 직접 바꾸는 것입니다.
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; 
         }
?>

4. 퀵 정렬
퀵 정렬은 언어로 표현하기 위해 배열에서 $a 값을 선택하고, 이를 비교합니다. 나머지 요소는 더 큰 $a가 배열 오른쪽에 배치되고, 그렇지 않으면 왼쪽 배열에 배치됩니다. 그런 다음 각각 왼쪽과 오른쪽을 재귀적으로 호출합니다. 즉, 왼쪽과 오른쪽을 세분화하고 마지막으로 배열을 병합합니다.
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
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. 힙 정렬
계속