Radix Sort의 PHP 정렬 알고리즘

이 글은 주로 PHP 정렬 알고리즘 Radix Sort를 소개합니다. PHP 기수 정렬 알고리즘의 원리, 구현 방법 및 관련 사용 기술을 예제 형식으로 자세히 분석합니다. 기사에서는 PHP 정렬 알고리즘의 Radix Sort를 설명합니다. 참고하실 수 있도록 자세한 내용을 공유합니다.

라딕스 정렬은 "Dahua 데이터 구조"에 언급되어 있지 않지만, 8가지 주요 정렬 알고리즘을 모으기 위해 제가 직접 인터넷을 통해 이 정렬 알고리즘을 배웠고, 당신과 공유했습니다.

기본 아이디어: 기수 정렬(radix sort)은 "버킷 정렬" 또는 bin 정렬이라고도 알려진 "배포 정렬"에 속하며 키를 사용합니다. 기수 정렬 방법은 안정적인 정렬이며 시간 복잡도는 O(nlog(r)m)입니다. 여기서 r은 기수입니다. m은 힙 수입니다. 특정 시점에서는 기수 정렬 방법이 다른 안정성 정렬 방법보다 더 효율적입니다.

사실 이 아이디어를 예를 통해 요약할 수는 없습니다.

기본 솔루션: PS: 여기서 소개하는 기수 정렬은 LSD(최하위 비트 우선)를 사용합니다. 물론 MSD(가장 중요한 것부터)가 있으며, Baidu에 가서 이들 간의 유사점과 차이점을 알아볼 수 있습니다.

이제 다음과 같은 숫자가 있다고 가정해 보겠습니다.

2 343 342 1 128 43 4249 814 687 654 3

우리는 기수 정렬을 사용하여 작은 숫자에서 큰 숫자로 정렬합니다.

첫 번째 단계는 먼저 값을 방문할 때 한 자리 값에 따라 0~9번 버킷에 할당하는 것입니다(앞에서 뒤로 방문하면 다음 단계는 동일함).

0 :

1 : 1 2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

두 번째 단계는 값을 추가하는 것입니다. ​​이 버킷에서 이들을 다시 연결하여 다음 순서를 형성합니다.

1 2 342 343 43 3 814 654 687 128 4249

3단계. 10자리 값에 따라 값을 방문합니다(앞에서 끝까지 방문). 뒤로, 다음 단계는 동일합니다.) 0~9번 버킷에 할당합니다.

0 : 1 2 3

1 : 8142 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

네 번째 단계는 이러한 버킷의 값을 다시 연결하여 다음 시퀀스를 형성하는 것입니다.

1 2 3 814 128 342 343 43 4249 654 687

5단계: 백 자리 값에 따라 해당 값을 방문할 때(앞에서 뒤로 방문하면 다음 단계는 동일함) 0~9번 버킷에 할당합니다.

0 : 1 2 3 43

1 : 1282 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

여섯번째 단계는 이 버킷을 함께 연결하면

1 2 3 43 128 4249 342 343 654 687 814

순서가 됩니다. . . . . . 모든 사람이 다음 단계를 수행할 수 있어야 합니다. 실제로 여섯 번째 단계에 도달할 때까지 정렬되지 않은 항목은 4249개만 남습니다.

위의 단계 중 많은 단계가 동일하므로 하나, 수십, 수백,,,,만 제어하면 됩니다.

코드를 살펴보겠습니다.

알고리즘 구현:

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//获取数组中的最大数
//就像上面的例子一样，我们最终是否停止算法不过就是看数组中的最大值：4249，它的位数就是循环的次数
function getMax(array $arr){
  $max = 0;
  $length = count($arr);
  for($i = 0;$i < $length;$i ++){
    if($max < $arr[$i]){
      $max = $arr[$i];
    }
  }
  return $max;
}
//获取最大数的位数,最大值的位数就是我们分配桶的次数
function getLoopTimes($maxNum){
  $count = 1;
  $temp = floor($maxNum / 10);
  while($temp != 0){
    $count ++;
    $temp = floor($temp / 10);
  }
  return $count;
}
/**
 * @param array $arr 待排序数组
 * @param $loop 第几次循环标识
 * 该函数只是完成某一位（个位或十位）上的桶排序
 */
function R_Sort(array &$arr,$loop){
  //桶数组，在强类型语言中，这个数组应该声明为[10][count($arr)]
  //第一维是 0-9 十个数
  //第二维这样定义是因为有可能待排序的数组中的所有数的某一位上的只是一样的，这样就全挤在一个桶里面了
  $tempArr = array();
  $count = count($arr);
  //初始化$tempArr数组
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除数
  //如798个位桶index=(798/1)%10=8
  //十位桶index=(798/10)%10=9
  //百位桶index=(798/100)%10=7
  //$tempNum为上式中的1、10、100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    //求出某位上的数字
    $row_index = ($arr[$i] / $tempNum) % 10;
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$row_index][$j] == NULL){
        $tempArr[$row_index][$j] = $arr[$i];   //入桶
        break;
      }
    }
  }
  //还原回原数组中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$i][$j] != NULL){
        $arr[$k ++] = $tempArr[$i][$j];  //出桶
        $tempArr[$i][$j] = NULL;  //避免下次循环的时候污染数据
      }
    }
  }
}
//最终调用的主函数
function RadixSort(array &$arr){
  $max = getMax($arr);
  $loop = getLoopTimes($max);
  //对每一位进行桶分配（1 表示个位，$loop 表示最高位）
  for($i = 1;$i <= $loop;$i ++){
    R_Sort($arr,$i);
  }
}

호출 알고리즘:

$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);

실행 결과:

array(11) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(43)
 [4]=>
 int(128)
 [5]=>
 int(342)
 [6]=>
 int(343)
 [7]=>
 int(654)
 [8]=>
 int(687)
 [9]=>
 int(814)
 [10]=>
 int(4249)
}

사실 제가 예전에 썼던 이 코드들이 꽤 기대가 되네요 , 오늘 블로그를 작성하면서 버킷이 실제로 대기열이라는 것을 알았으므로 위의

이 가장 적합하며 여기서는 단순화를 위해 사용하지 않겠습니다):

R_Sort()函数复杂了，我们使用 array_push() 和 array_shift() 来重写该方法（当然，要模拟队列的话，用 SPL 提供的 splqueue

function R_Sort(array &$arr,$loop){
  $tempArr = array();
  $count = count($arr);
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除数
  //如798个位桶index=(798/1)%10=8
  //十位桶index=(798/10)%10=9
  //百位桶index=(798/100)%10=7
  //$tempNum为上式中的1、10、100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    //求出某位上的数字
    $row_index = ($arr[$i] / $tempNum) % 10;
    //入桶
    array_push($tempArr[$row_index],$arr[$i]);
  }
  //还原回原数组中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    //出桶
    while(count($tempArr[$i]) > 0){
      $arr[$k ++] = array_shift($tempArr[$i]);
    }
  }
}

기수 정렬 방법은 안정적인 정렬 및 시간 복잡성은

O (nlog(r)m)

입니다. 여기서 r은 취한 기수이고 m은 힙 수입니다. 관련 권장 사항:

PHP 정렬 알고리즘 Quick Sort(Quick Sort) 및 최적화

PHP 정렬 알고리즘 Merging Sort(Merging Sort)

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

위 내용은 Radix Sort의 PHP 정렬 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!