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. 힙 정렬
계속
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
