기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합
- 青灯夜游앞으로
- 2020-07-16 16:16:332262검색
많은 사람들은 알고리즘이 프로그램의 핵심이라고 말합니다. 프로그램이 더 나은지 나쁜지의 핵심은 알고리즘의 품질입니다. 주니어 PHPer로서 알고리즘에 대한 노출은 거의 없습니다. 하지만 버블정렬, 삽입정렬, 선택정렬, 퀵정렬, 병합정렬 등의 기본 알고리즘을 숙지해야 합니다.
요구 사항: 버블 정렬, 퀵 정렬, 선택 정렬, 삽입 정렬, 병합 정렬을 사용하여 아래 배열의 값을 작은 것부터 큰 것 순으로 정렬하세요.
$arr=array(11,3,56,62,21,66,32,78, 36,76 , 39, 88, 34) 1. 소개: 버블 정렬(Bubble Sort)은 간단합니다. 정렬 알고리즘. 정렬할 시퀀스를 반복적으로 살펴보고 두 요소를 차례로 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다. 단계: 1. 인접한 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요. 2. 처음의 첫 번째 쌍부터 끝의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다. 3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다. 4. 비교할 숫자 쌍이 없을 때까지 점점 더 적은 수의 요소에 대해 위 단계를 계속 반복합니다. 코드:
<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합
function bubbleSort($arr) {
$len = count($arr);
//该层循环控制 需要冒泡的轮数
for ($i = 1; $i < $len; $i++) {
//该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($k = 0; $k < $len - $i; $k++) {
if ($arr[$k] > $arr[$k + 1]) { //从小到大
$tmp = $arr[$k + 1]; // 声明一个临时变量
$arr[$k + 1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
$arr = bubbleSort($arr);
print_r($arr); 정렬 효과:
2. 선택 정렬
소개:
선택 정렬은 다음과 같습니다. 간단하고 직관적인 정렬 알고리즘. 작동 방식은 다음과 같습니다. 먼저 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 계속해서 가장 작은 요소를 찾아 정렬된 시퀀스의 끝에 넣습니다. 모든 요소가 정렬될 때까지 계속됩니다.코드:
<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합
//实现思路 双重循环完成，外层控制轮数，当前的最小值。内层控制比较次数
function selectSort($arr) {
$len = count($arr);
//$i 当前最小值的位置， 需要参与比较的元素
for ($i = 0; $i < $len - 1; $i++) {
//先假设最小的值的位置
$p = $i;
//$j 当前都需要和哪些元素比较，$i 后边的。
for ($j = $i + 1; $j < $len; $j++) {
//$arr[$p] 是 当前已知的最小值
//比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
$p = ($arr[$p] <= $arr[$j]) ? $p : $j;
}
//已经确定了当前的最小值的位置，保存到$p中。
//如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
if ($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最终结果
return $arr;
}
$arr = selectSort($arr);
print_r($arr);3. 삽입 정렬 
소개:
삽입 정렬의 알고리즘 설명은 간단하고 직관적입니다. 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 여분의 공간만 사용하는 정렬)이 사용되므로 스캔 과정에서 뒤에서 앞으로 반복적으로 점진적으로 이동해야 합니다. 요소를 뒤로 정렬하여 최신 요소에 대한 삽입 공간을 제공합니다.단계:
1. 첫 번째 요소부터 정렬된 것으로 간주할 수 있습니다2. 정렬된 요소 순서에서 뒤에서 앞으로 스캔합니다. 정렬된 요소가 새 요소보다 크면 요소를 다음 위치로 이동합니다
4. 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복합니다. 해당 위치에 새 요소 추가 Medium
6. 2단계를 반복하세요
<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//插入排序
function insert_sort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
//获得当前需要比较的元素值
$tmp = $arr[$i];
//内层循环控制 比较 并 插入
for($j=$i-1; $j>=0; $j--) {
//$arr[$i];需要插入的元素
//$arr[$j];需要比较的元素
if($tmp
{
//发现插入的元素要小，交换位置
//将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组，则前面的就不需要再次比较了。
break;
}
}
}
//将这个元素 插入到已经排序好的序列内。
//返回
return $arr;
}
$arr = insert_sort($arr);
print_r($arr);4. 소개:기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
步骤：
1、从数列中挑出一个元素，称为 “基准”（pivot），
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码：
<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합
function quick_sort($arr)
{
//判断参数是否是一个数组
if(!is_array($arr)) return false;
//递归出口:数组长度为1，直接返回数组
$length = count($arr);
if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
$left = $right = array();
//使用for循环进行遍历，把第一个元素当做比较的对象
for($i=1; $i<$length; $i++)
{
//判断当前元素的大小
if($arr[$i] < $arr[0]){ //从小到大 < || 从大到小 >
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//递归调用
$left=quick_sort($left);
$right=quick_sort($right);
//将所有的结果合并
return array_merge($left,array($arr[0]),$right);
}
$arr = quick_sort($arr);
print_r($arr);排序效果：
5、기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합
利用递归，先拆分、后合并、再排序。
步骤:
- 均分数列为两个子数列
- 递归重复上一步骤，直到子数列只有一个元素
- 父数列合并两个子数列并排序，递归返回数列
代码：
<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
// 기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합主程序
function mergeSort($arr) {
$len = count($arr);
// 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
if ($len <= 1) {
return $arr;
}
$mid = intval($len / 2); // 取数组中间
$left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
$right= array_slice($arr, $mid); // 拆分数组mid-末尾这部分给右边right
$left = mergeSort($left); // 左边拆分完后开始递归合并往上走
$right= mergeSort($right); // 右边拆分完毕开始递归往上走
$arr = merge($left, $right); // 合并两个数组,继续递归
return $arr;
}
// merge函数将指定的两个有序数组(arrA, arr)合并并且排序
function merge($arrA, $arrB) {
$arrC = array();
while (count($arrA) && count($arrB)) {
// 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
// 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
//从小到大 < || 从大到小 >
$arrC[] = $arrA[0] <p>排序效果：</p><p> </p><p><img src="https://img.php.cn/upload/article/000/000/024/4059d12f5632ac9f990ed52b74747d4b-4.gif" alt="기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합" style="max-width:90%" style="max-width:90%"></p><p>相关推荐：<a href="https://www.php.cn/" target="_blank">PHP教程</a><br></p>위 내용은 기본 PHP 알고리즘에 대한 자세한 설명: 버블링, 선택, 삽입, 빠른, 병합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!