> php教程 > php手册 > 본문

단일 크기 및 단일 크기 배열에 대한 버블 정렬 및 문제 발생

WBOY
풀어 주다: 2016-08-08 08:49:49
원래의
1576명이 탐색했습니다.

버블정렬

버블 정렬은 컴퓨터 과학 분야의 비교적 간단한 정렬 알고리즘입니다.

버블 정렬 알고리즘은 다음과 같이 작동합니다. (뒤에서 앞으로)

  1. 인접한 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.
  2. 첫 번째 쌍에서 시작하여 마지막 쌍으로 끝나는 각 인접 요소 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.
  3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
  4. 비교할 숫자 쌍이 더 이상 없을 때까지 매번 요소 수를 줄여 위 단계를 계속 반복합니다.

l 인접한 두 요소를 차례로 비교하여 역순을 제거합니다(역순은 수학적 개념이며 쌍으로 나타납니다. 예를 들어 50과 30은 역순의 쌍입니다. 소위 역순 제거는 다음을 의미합니다. 큰 것은 뒤에, 작은 것은 (앞에 놓는다)

l 이렇게 해서 한 번 비교한 결과 가장 큰 쌍이 마지막에 있습니다!

l 그런 다음 새로운 비교 라운드를 계속합니다. 이전 라운드 이후의 최대값은 더 이상 비교에 참여하지 않습니다. 이번 라운드의 비교는 이전 라운드보다 높을 것입니다. , 등 비교할 값이 두 개만 남을 때까지 !

그래서

이중 루프입니다. 외부 레이어는 라운드 수를 제어하고 내부 레이어는 각 라운드의 비교 수를 제어합니다.

배열에 n개의 요소가 있는 경우 총 n-1번의 비교 라운드가 필요하며, 이는 외부 루프의 수입니다!

다른 지식 포인트 추가:

목록 — 배열의 값을 작은 것부터 큰 것까지 일부 변수에 할당하고 차례로 큰 값에서 작은 값으로 값을 할당합니다

내가 작성한 버블 정렬에 대해 이야기하고 이에 대해 내가 이해한 내용을 설명하겠습니다.

<span style="color: #008000;">//</span><span style="color: #008000;">冒泡排序,让数组从小到大依次排序</span>
<span style="color: #000000;">function maopao($arr){
    </span><span style="color: #008000;">//</span><span style="color: #008000;">双层循环,外层控制,$i代表循环的轮数,比较轮数等于数组的个数减1,$i<$len相当于数组个数-1,例如8个,当$i=7是最后的比较,符合8-1=7;</span>
    <span style="color: #0000ff;">for</span>($i=<span style="color: #800080;">1</span>,$len=count($arr);$i<$len;$i++<span style="color: #000000;">){
        </span><span style="color: #008000;">//</span><span style="color: #008000;">内层控制每一轮比较的次数,$k=下标,每一轮比较完最后一个将不再参与比较,下标从0开始</span>
        <span style="color: #0000ff;">for</span>($k=<span style="color: #800080;">0</span>;$k<$len-$i;$k++<span style="color: #000000;">){
            </span><span style="color: #008000;">//</span><span style="color: #008000;">比较相邻的两个数,如果前面的数值比后面的大就调换下位置,通过中间数,如果不比它大,则不用调换</span>
            <span style="color: #0000ff;">if</span>($arr[$k]>$arr[$k+<span style="color: #800080;">1</span><span style="color: #000000;">]){
                </span><span style="color: #008000;">//</span><span style="color: #008000;">调换位置</span>
                $tem=<span style="color: #000000;">$arr[$k];
                $arr[$k]</span>=$arr[$k+<span style="color: #800080;">1</span><span style="color: #000000;">];
                $arr[$k</span>+<span style="color: #800080;">1</span>]=<span style="color: #000000;">$tem;
            }
        }
    }
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> $arr;
}
$arr1</span>=array(<span style="color: #800080;">45</span>,<span style="color: #800080;">85</span>,<span style="color: #800080;">12</span>,<span style="color: #800080;">22</span>,<span style="color: #800080;">36</span>,<span style="color: #800080;">7</span>,<span style="color: #800080;">75</span>,<span style="color: #800080;">15</span>,<span style="color: #800080;">40</span>,<span style="color: #800080;">64</span><span style="color: #000000;">);
</span><span style="color: #008000;">//</span><span style="color: #008000;"> echo count($arr1);</span>
echo <span style="color: #800000;">'</span><span style="color: #800000;"><pre class="brush:php;toolbar:false"></span><span style="color: #800000;">'</span><span style="color: #000000;">;
print_r(maopao($arr1));</span></span>
로그인 후 복사

효과:

작은 배열에서 큰 배열로 정렬 달성

큰 것부터 작은 것까지 구현하려면 동일한 알고리즘을 사용하며 중간 숫자의 비교를 통해 모두 교환됩니다.

다음으로 제가 인터뷰에서 겪었던 문제에 대해 이야기해 보겠습니다. 배열을 사용하여 첫 번째 것을 가장 크게 만들고, 두 번째를 가장 작게 만들고, 세 번째를 두 번째로 크고, 네 번째를 두 번째로 작게 만듭니다. 이런 식으로 정렬하세요.

그때는 그런 게 있는 것 같다고만 생각했어요

array_pop: 배열의 마지막 데이터를 팝합니다

array_shift: 배열 앞쪽에서 데이터를 팝합니다.

배열을 큰 것부터 작은 것 순으로 정렬한 후, 첫 번째 것을 꺼내서 가장 큰 것을 얻고, 마지막 것을 꺼내서 가장 작은 것을 얻고, 이 둘을 합쳐서 가장 큰 것과 가장 작은 것을 얻은 다음, 다 가져갈 때까지 계속 이렇게 꺼내세요.

돌아가서 이것이 가능한지 확인해 보겠습니다. 이제 제가 시도한 방법에 대해 이야기하겠습니다

예:

그래서

첫 번째 단계: 먼저 버블링을 통해 배열을 큰 것부터 작은 것까지 정렬합니다

두 번째 단계 첫 번째(가장 큰) 팝업과 마지막(가장 작은) 팝업을 재귀적으로 합친 다음 다 꺼낼 때까지 꺼냅니다.

효과:

더 좋은 방법이 있는데, 제가 그때 생각난 방법이에요. 하, 화내지 말고 편하게 불평하세요.

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 추천
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿