[PHP 인터뷰] 면접에서 반드시 물어봐야 할 두 가지 단순 정렬 알고리즘, 버블 정렬과 퀵 정렬에 대한 설명

little bottle

풀어 주다： 2023-04-05 22:08:01

앞으로

2444명이 탐색했습니다.

일반적으로 면접을 볼 때 면접 질문에 답변하는데 문제가 없습니다. PHP 개발자는 자신이 수행하는 프로젝트에 대해 잘 아는 것 외에도 기본 알고리즘을 이해해야 합니다. PHP 인터뷰에서 자주 물어보는 알고리즘인 버블정렬과 퀵정렬을 공유해보겠습니다.

버블 정렬: 일대일 비교 정렬

기본 아이디어:

정렬할 요소의 열을 반복해서 방문하여 인접한 두 요소를 차례로 비교하고 순서가 작은) 오류가 발생하면 교환하세요. 요소를 방문하는 작업은 인접한 요소를 교환할 필요가 없을 때까지 반복됩니다. 이는 요소가 정렬되었음을 의미합니다.

그림:

1. 처음: 배열의 첫 번째 요소를 가져와 두 번째 요소부터 비교합니다. 앞 요소가 뒤 요소보다 크면 두 요소를 바꿉니다. 요소, 더 큰 값을 얻고, 계속해서 거꾸로 비교하고, 배열 요소가 끝날 때까지 버블링을 달성합니다(한 번 버블링하고, 현재 "나머지" 배열의 최대값을 가져와 배열의 "끝"에 넣습니다) ) )

2. 두 번째부터 비교는 여전히 첫 번째 요소부터 시작되지만 배열의 길이만 -1이고 매번 비교 횟수는 차례로 -1입니다.

3. 끝까지 비교하기 위해 여러 숫자를 비교할 필요는 없습니다.

코드:

$arr = array(3,2,6,0,1,4,7);
        //因为排序需要每次将一个元素与数组的其他元素进行比较，所以需要两层循环来控制
        //外层循环控制冒泡次数
        //内存循环比较每次的大小，得到每次的最大值（泡）
 
        for($i = 0,$length = count($arr);$i < $length;$i++){
        
                 //内存循环
                 for($j = 0;$j < ($length - $i - 1);$j++){
                         //拿着j变量所对应的数组元素，与后面的元素进行比较
                         if($arr[$j] > $arr[$j + 1]){
                                  //交换位置
                                  $temp              = $arr[$j];
                                  $arr[$j]           = $arr[$j+1];
                                  $arr[$j+1]         = $temp;
                         }
                 }
        }

로그인 후 복사

요약:

버블 정렬의 가장 좋은 시간 복잡도는 O(n)입니다. 비록 최적의 알고리즘은 아니지만 말입니다. 과 자주 접하게 되는데, 인터뷰에서도 질문을 받기 때문에 기본 원리를 이해하고, 이해할 수 있어야 하며, 쓸 수 있어야 합니다

빠른 정렬: 시간을 위한 공간 교환

기본 아이디어:

하나의 정렬 패스를 통해 정렬된 데이터는 두 개의 독립적인 부분으로 나누어집니다. 한 부분의 모든 데이터는 다른 부분의 모든 데이터보다 작습니다. 그런 다음 데이터의 두 부분이 빠르게 정렬됩니다. 이 방법을 사용하면 전체 정렬 과정이 반복적으로 수행될 수 있습니다.

그림:

기본적으로 두 개의 새로운 빈 배열을 만들고 전체 배열 요소를 순회합니다. 그런 다음 이를 넣습니다. 더 큰 배열이 필요하면 다른 배열에 넣으세요

재귀적 아이디어

1. 재귀 지점: 두 배열의 요소가 1보다 크면 다시 분해해야 합니다

2 . 재귀적 종료: 배열 요소가 1이 되는 경우

코드:

//待排序数组
        $arr = array(5,3,8,2,6,4,7);
        //函数实现快速排序
        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);
        }

로그인 후 복사