PHP_php 팁에 구현된 일반적인 정렬 알고리즘 요약

이 글은 알고리즘을 설계할 때 좋은 참고 가치가 있는 일반적인 PHP 정렬 알고리즘을 요약한 것입니다. 이제 참고용으로 모든 사람과 공유하세요. 세부 내용은 다음과 같습니다.

1. 삽입 정렬

텍스트를 사용하여 간단히 설명하세요. 예: $arr = array(4,2,4,6,3,6,1,7,9) 숫자 그룹을 순서대로 정렬합니다.
따라서 먼저 배열의 두 번째 요소를 첫 번째 요소와 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 두 요소의 위치를 ​​바꿉니다. 그런 다음 배열의 세 번째 요소를 가져와 첫 번째 요소와 비교합니다. 두 번째, 첫 번째 요소를 비교하고 세 번째 요소가 더 작으면 교체합니다. 등. 이는 삽입 정렬이며 시간 빈도는 1 2... (n-1)=(n^2)/2입니다. 그러면 시간 복잡도는 O(n^2)입니다.

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

<&#63;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; 
 }
&#63;>

2. 선택 정렬

선택 정렬이 언어로 설명된 경우 다음과 같이 될 수 있습니다. $arr = array(4,3,5,2,1);

먼저 첫 번째 배열과 다음 배열을 모두 비교하여 가장 작은 숫자를 찾은 후 첫 번째 배열과 교환합니다(물론, 가장 작은 것이 첫 번째 배열이라면 교환할 필요가 없습니다) it), 그런 다음 루프를 반복합니다. 즉, 두 번째 숫자를 다음 숫자와 비교하여 가장 작은 숫자를 찾은 다음 두 번째 숫자와 교환하는 식으로 계속 진행합니다. 즉, 매번 가장 작은 남은 값을 찾습니다. 얻을 수 있습니다: 처음에는 시간 빈도가 n입니다. (첫 번째는 다음 n-1과 비교하여 가장 작은 것을 찾은 다음 첫 번째인지 확인하고 그렇지 않으면 교환합니다.) future , 마이너스 1이 뒤따릅니다. 시간 복잡도도 O(n^2)입니다.

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

<&#63;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; 
 }
&#63;>

3. 버블정렬
 
실제로 버블 정렬과 선택 정렬 간에는 큰 차이가 없습니다. 가장 작은 것을 찾아 가장 왼쪽에 놓습니다. 문제를 순서대로 풀어보세요. 차이점은 버블 정렬은 위치를 더 많이 바꾸는 반면 선택 정렬은 가장 작은 요소의 첨자를 찾은 다음 가장 왼쪽 요소와 위치를 직접 바꾸는 것입니다.

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

<&#63;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; 
 }
&#63;>

4. 퀵 정렬

퀵 정렬은 언어로 설명하기 위해 배열에서 $a 값을 선택한 후 다른 요소와 비교하여 $a보다 큰 값이 배열 오른쪽에 배치되고, 그 반대의 경우도 마찬가지입니다. 왼쪽 배열에 있습니다. 그런 다음 각각 왼쪽과 오른쪽을 재귀적으로 호출합니다. 즉, 왼쪽과 오른쪽을 세분화하고 마지막으로 배열을 병합합니다.

php 빠른 정렬:

<&#63;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; 
 }
&#63;>

5. 병합 정렬

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

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

<&#63;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] &#63; array_shift($right) : array_shift($left);
        //进行比较，小的移除，并且放入到数组$m中。
    }
    return arr_merge($m,$left,$right);//进行合并（由于不知道left right 哪个会为空，所以进行统一合并）
}

&#63;>

6. 힙 정렬

이 예에서 fixDown 함수는 특정 노드의 하향 조정을 구현합니다. 여기서 기본값은 시작 노드가 1이며 이는 상위 노드와 하위 노드 간의 관계를 계산하는 데 편리합니다.

참고:

시작 노드가 1인 부모-자식 관계: 부모 노드 k, 자식 노드는 2K, 2k 1 자식 노드 j, 부모 노드는 바닥(j/2) 바닥은 반내림
시작 노드가 0인 부모-자식 관계: 부모 노드 k, 자식 노드는 2K 1, 2k 2 자식 노드 j, 부모 노드는 Floor((j-1)/2)

매개변수 $k는 조정점 위치, $lenth는 배열의 길이로 1부터 마지막 ​​노드까지의 좌표입니다.

<&#63;php
function fixDown(&$arr, $k, $lenth)
{
　　while(2*$k<=$lenth) { //只要当前节点有子节点， 就需要继续该循环
    $j = $k*2;
    if ($j<$lenth && $arr[$j]<$arr[$j+1]) $j++;  // 只要子节点有右节点，且右节点比左节点大，那么切换到右节点操作。
    if ($arr[$j] < $arr[$k]) break; // 如果子节点都没有父节点大， 那么调整结束。
    exch($arr[$j], $arr[$k]);
　　　  $k = $j;
  }
}

function exch(&$a, &$b) {
  $tmp = $a; $a = $b; $b = $tmp;
}

function headSort(&$arr)
{
  $len = count($arr);
  array_unshift($arr, NULL);
  for($i=$len/2;$i>=1;$i--) {
    fixDown($arr, $i, $len);
  }
  while($len>1) {
    exch($arr[1], $arr[$len]);
    fixDown($arr, 1, --$len);
  }
  array_shift($arr);
}
$arr = array(4,6,4,9,2,3);
headSort($arr);
&#63;>

이 기사에 설명된 정렬 알고리즘의 예가 모든 사람의 PHP 프로그래밍에 도움이 되기를 바랍니다.