지역 사회
배우다
도구 라이브러리
AI 도구
여가
찾다
한국어
집 백엔드 개발 PHP 튜토리얼 PHP는 php7 PHP 환경 구축에서 고전적인 알고리즘을 구현합니다. PHP 입문부터 숙련까지

PHP는 php7 PHP 환경 구축에서 고전적인 알고리즘을 구현합니다. PHP 입문부터 숙련까지

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jul 29, 2016 am 08:53 AM
php

머리말

며칠 전 PHP를 통해 다양한 정렬 알고리즘을 구현하고 해당 알고리즘의 시간 소모를 비교했습니다.
[알고리즘] PHP는 고전적인 알고리즘을 구현합니다(1부)

다음 알고리즘을 구현해 보겠습니다

  • 힙 정렬
  • 칵테일 정렬
  • 직접 선택 sort
  • 카운팅 정렬

CODE

<code><span>$arr</span> = [];

<span>for</span> (<span>$i</span> = <span>0</span>; <span>$i</span> < <span>5000</span>; <span>$i</span>++) {
    <span>$arr</span>[] = rand(<span>1</span>, <span>50000</span>);
}



<span>// 5 堆排序</span><span>/**
 * 交换两个数的位置
 *<span> @param</span> $a
 *<span> @param</span> $b
 */</span><span><span>function</span><span>swap</span><span>(&<span>$a</span>,&<span>$b</span>)</span>{</span><span>$temp</span> = <span>$b</span>;
    <span>$b</span> = <span>$a</span>;
    <span>$a</span> = <span>$temp</span>;
}

<span>/**
 * 左子树
 *<span> @param</span> $i
 *<span> @return</span> mixed
 */</span><span><span>function</span><span>lchild</span><span>(<span>$i</span>)</span>{</span><span>return</span><span>$i</span>*<span>2</span>+<span>1</span>;}

<span>/**
 * 右子树
 *<span> @param</span> $i
 *<span> @return</span> mixed
 */</span><span><span>function</span><span>rchild</span><span>(<span>$i</span>)</span>{</span><span>return</span><span>$i</span>*<span>2</span>+<span>2</span>;}

<span>/**
 * 整理节点
 *<span> @param</span> $array 待调整的堆数组
 *<span> @param</span> $i 待调整的数组元素的位置
 *<span> @param</span> $heapsize  数组的长度
 */</span><span><span>function</span><span>build_heap</span><span>(&<span>$array</span>,<span>$i</span>,<span>$heapsize</span>)</span>{</span><span>$left</span> = lchild(<span>$i</span>);
    <span>$right</span> = rchild(<span>$i</span>);
    <span>$max</span> = <span>$i</span>;
    <span>//如果比左子树小并且在左右子树的右面,边界调整到左侧</span><span>if</span>(<span>$i</span> < <span>$heapsize</span> && <span>$left</span> < <span>$heapsize</span>  && <span>$array</span>[<span>$left</span>] > <span>$array</span>[<span>$i</span>] ){
        <span>$max</span> = <span>$left</span>;
    }

    <span>//如果比右子树小并且都小于要构建的数组长度,边界调整到右侧</span><span>if</span>(<span>$i</span> < <span>$heapsize</span> && <span>$right</span> < <span>$heapsize</span> && <span>$array</span>[<span>$right</span>] > <span>$array</span>[<span>$max</span>]){
        <span>$max</span> = <span>$right</span>;
    }

    <span>//如果经过两次调整后,要调整的数组不是最大值</span><span>if</span>(<span>$i</span> != <span>$max</span> && <span>$i</span> < <span>$heapsize</span> && <span>$max</span> < <span>$heapsize</span>){

        <span>//就交换对应的位置,并再次进行整理节点</span>
        swap(<span>$array</span>[<span>$i</span>],<span>$array</span>[<span>$max</span>]);
        build_heap(<span>$array</span>,<span>$max</span>,<span>$heapsize</span>);

    }
}

<span>/**
 * 对堆进行排序
 *<span> @param</span> $array 要排序的数组
 *<span> @param</span> $heapsize 数组的长度
 */</span><span><span>function</span><span>sortHeap</span><span>(&<span>$array</span>,<span>$heapsize</span>)</span>{</span><span>while</span>(<span>$heapsize</span>){ <span>//长度逐步递减0</span><span>//首先交换第一个元素和最后一个元素的位置</span>
        swap(<span>$array</span>[<span>0</span>],<span>$array</span>[<span>$heapsize</span>-<span>1</span>]);
        <span>$heapsize</span> = <span>$heapsize</span> -<span>1</span>;
        build_heap(<span>$array</span>,<span>0</span>,<span>$heapsize</span>); <span>//整理数组的第一个的元素的位置,长度为逐步递减的数组长度</span>
    }
}

<span>/**
 * 创建堆
 *<span> @param</span> $array
 *<span> @param</span> $heapsize
 */</span><span><span>function</span><span>createHeap</span><span>(&<span>$array</span>,<span>$heapsize</span>)</span>{</span><span>$i</span> = ceil(<span>$heapsize</span>/<span>2</span>)-<span>1</span>; <span>//找到中间的位置</span><span>for</span>( ; <span>$i</span>>=<span>0</span> ;<span>$i</span>-- ){  <span>//从中间往前面整理堆</span>
        build_heap(<span>$array</span>,<span>$i</span>,<span>$heapsize</span>);
    }
}

<span>/**
 * 堆排序主函数
 */</span><span><span>function</span><span>Heapsort</span><span>(<span>$array</span>)</span>{</span><span>$heapsize</span> = count(<span>$array</span>);
    createHeap(<span>$array</span>,<span>$heapsize</span>);
    sortHeap(<span>$array</span>,<span>$heapsize</span>);

    <span>return</span><span>$array</span>;

}



<span>$heapsort_start_time</span> = microtime(<span>true</span>);

<span>$heapsort_sort</span> = Heapsort(<span>$arr</span>);

<span>$heapsort_end_time</span> = microtime(<span>true</span>);

<span>$heapsort_need_time</span> = <span>$heapsort_end_time</span> - <span>$heapsort_start_time</span>;

print_r(<span>"堆排序耗时:"</span> . <span>$heapsort_need_time</span> . <span>"<br />"</span>);


<span>// 6 鸡尾酒排序法</span><span>/**
 * 鸡尾酒排序
 *<span> @param</span> $arr
 *<span> @return</span> mixed
 */</span><span><span>function</span><span>Cocktailsort</span><span>(<span>$arr</span>)</span> {</span><span>$arr_len</span>  =count(<span>$arr</span>);

    <span>for</span>(<span>$i</span> = <span>0</span> ; <span>$i</span> < (<span>$arr_len</span>/<span>2</span>) ; <span>$i</span> ++){
        <span>//将最小值排到队尾</span><span>for</span>( <span>$j</span> = <span>$i</span> ; <span>$j</span> < ( <span>$arr_len</span> - <span>$i</span> - <span>1</span> ) ; <span>$j</span> ++ ){
            <span>if</span>(<span>$arr</span>[<span>$j</span>] < <span>$arr</span>[<span>$j</span> + <span>1</span>] ){
                swap(<span>$arr</span>[<span>$j</span>],<span>$arr</span>[<span>$j</span> + <span>1</span>]);
            }
        }
        <span>//将最大值排到队头</span><span>for</span>(<span>$j</span> = <span>$arr_len</span> - <span>1</span> - (<span>$i</span> + <span>1</span>); <span>$j</span> > <span>$i</span> ; <span>$j</span> --){
            <span>if</span>(<span>$arr</span>[<span>$j</span>] > <span>$arr</span>[<span>$j</span> - <span>1</span>]){
                swap(<span>$arr</span>[<span>$j</span>],<span>$arr</span>[<span>$j</span> - <span>1</span>]);
            }
        }
    }
    <span>return</span><span>$arr</span>;
}

<span>$cocktailsort_start_time</span> = microtime(<span>true</span>);

<span>$cocktailsort_sort</span> = Cocktailsort(<span>$arr</span>);

<span>$cocktailsortt_end_time</span> = microtime(<span>true</span>);

<span>$cocktailsort_need_time</span> = <span>$cocktailsortt_end_time</span> - <span>$cocktailsort_start_time</span>;

print_r(<span>"鸡尾酒排序耗时:"</span> . <span>$cocktailsort_need_time</span> . <span>"<br />"</span>);


<span>// 7  希尔排序</span><span>/**
 * 希尔排序
 *<span> @param</span> $arr
 */</span><span><span>function</span><span>Shellsort</span><span>(<span>$arr</span>)</span>
{</span><span>$n</span>=count(<span>$arr</span>); <span>//数组长度</span><span>for</span>(<span>$gap</span>=floor(<span>$n</span>/<span>2</span>);<span>$gap</span>><span>0</span>;<span>$gap</span>=floor(<span>$gap</span>/=<span>2</span>)) <span>//</span>
    {
        <span>for</span>(<span>$i</span>=<span>$gap</span>;<span>$i</span><<span>$n</span>;++<span>$i</span>) <span>//根据增量循环</span>
        {
            <span>//以增量为步幅进行查看</span><span>for</span>( <span>$j</span>=<span>$i</span>-<span>$gap</span>; <span>$j</span>>=<span>0</span> && <span>$arr</span>[<span>$j</span>+<span>$gap</span>] < <span>$arr</span>[<span>$j</span>]; <span>$j</span> -= <span>$gap</span>)
            {
                swap(<span>$arr</span>[<span>$j</span>],<span>$arr</span>[<span>$j</span>+<span>$gap</span>]);
            }
        }
    }

    <span>return</span><span>$arr</span>;
}

<span>$shellsort_start_time</span> = microtime(<span>true</span>);

<span>$shellsort_sort</span> = Cocktailsort(<span>$arr</span>);

<span>$shellsort_end_time</span> = microtime(<span>true</span>);

<span>$shellsort_need_time</span> = <span>$shellsort_end_time</span> - <span>$shellsort_start_time</span>;

print_r(<span>"希尔排序耗时:"</span> . <span>$shellsort_need_time</span> . <span>"<br />"</span>);

<span>// 8  直接选择排序</span><span>/**
 * 直接选择排序
 *<span> @param</span> $arr
 *<span> @return</span> mixed
 */</span><span><span>function</span><span>Straightselectsort</span><span>(<span>$arr</span>)</span>{</span><span>$n</span> = count(<span>$arr</span>);

    <span>for</span>(<span>$i</span> = <span>0</span> ; <span>$i</span> < <span>$n</span> - <span>1</span>;<span>$i</span>++){
        <span>$m</span> = <span>$i</span>;
        <span>for</span>(<span>$j</span> = <span>$i</span>+<span>1</span> ; <span>$j</span> < <span>$n</span>; <span>$j</span>++){
            <span>if</span>(<span>$arr</span>[<span>$j</span>] < <span>$arr</span>[<span>$m</span>] ){
                <span>$m</span> = <span>$j</span>;
            }

            <span>if</span>(<span>$m</span> != <span>$j</span>){
                <span>//进行交换</span>
                swap(<span>$arr</span>[<span>$m</span>],<span>$arr</span>[<span>$j</span>]);
            }
        }
    }
    <span>return</span><span>$arr</span>;
}

<span>$straightselectsort_start_time</span> = microtime(<span>true</span>);

<span>$straightselectsort_sort</span> = Cocktailsort(<span>$arr</span>);

<span>$straightselectsort_end_time</span> = microtime(<span>true</span>);

<span>$straightselectsort_need_time</span> = <span>$straightselectsort_end_time</span> - <span>$straightselectsort_start_time</span>;

print_r(<span>"直接选择排序耗时:"</span> . <span>$straightselectsort_need_time</span> . <span>"<br />"</span>);


<span>// 9  计数排序</span><span>/**
 * 计数排序
 *<span> @param</span> $arr
 *<span> @return</span> mixed
 */</span><span><span>function</span><span>Countsort</span><span>(<span>$arr</span>)</span>{</span><span>$max</span> = <span>$arr</span>[<span>0</span>];
    <span>$min</span> = <span>$arr</span>[<span>0</span>];

    <span>foreach</span>(<span>$arr</span><span>as</span><span>$key</span> => <span>$value</span>) {
        <span>if</span> (<span>$value</span> > <span>$max</span>) {
            <span>$max</span> = <span>$value</span>;
        }
        <span>if</span> (<span>$value</span> < <span>$min</span>) {
            <span>$min</span> = <span>$value</span>;
        }
    }
        <span>//这里k的大小是要排序的数组中，元素大小的极值差+1</span><span>$c</span>=[];
        <span>$k</span> = <span>$max</span> - <span>$min</span> + <span>1</span>;
        <span>for</span>(<span>$i</span> = <span>0</span>; <span>$i</span> < count(<span>$arr</span>) ; <span>$i</span> ++){
            <span>$c</span>[<span>$arr</span>[<span>$i</span>] - <span>$min</span> ] +=<span>1</span>;
        }

        <span>for</span>(<span>$i</span>=<span>1</span>;<span>$i</span> < count(<span>$c</span>); ++<span>$i</span>){
            <span>$c</span>[<span>$i</span>] = <span>$c</span>[<span>$i</span>] + <span>$c</span>[<span>$i</span> - <span>1</span>];
        }

        <span>for</span>(<span>$i</span> = count(<span>$arr</span>);<span>$i</span> > <span>0</span> ; --<span>$i</span>){
            <span>$b</span>[ -- <span>$c</span>[<span>$arr</span>[<span>$i</span>] - <span>$min</span>] ] = <span>$arr</span>[<span>$i</span>];
        }

    <span>return</span><span>$b</span>;
}

<span>$countsort_start_time</span> = microtime(<span>true</span>);

<span>$countsort_sort</span> = Cocktailsort(<span>$arr</span>);

<span>$countsort_end_time</span> = microtime(<span>true</span>);

<span>$countsort_need_time</span> = <span>$countsort_end_time</span> - <span>$countsort_start_time</span>;

print_r(<span>"计数排序耗时:"</span> . <span>$countsort_need_time</span> . <span>"<br />"</span>);


</code>
로그인 후 복사

시간이 많이 걸리는 비교

힙 정렬 시간이 많이 소요됨: 0.086709976196289
칵테일 정렬 시간: 4.6467659473419
힐 정렬 시간: 4.4215688705444
직접 선택 정렬 시간: 4.529422044754
정렬하는 데 시간이 걸립니다. 4.2601070404053

참조

  • 알고리즘 소개
').addClass('pre-numbering').hide (); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadeIn(1700); }); });

위 내용은 PHP 콘텐츠를 포함하여 PHP의 고전적인 알고리즘 구현을 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

더보기

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
어 ass 신 크리드 그림자 : 조개 수수께끼 솔루션
1 몇 주 전 By DDD
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Atomfall에서 크레인 제어 키 카드를 찾을 수 있습니다
1 몇 주 전 By DDD
더보기

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

더보기

뜨거운 주제

Gmail 이메일의 로그인 입구는 어디에 있나요?
7442
15
Cakephp 튜토리얼
1371
52
Steam의 계정 이름 형식은 무엇입니까?
76
11
Win11 활성화 키 영구
38
19
NYT 연결 힌트와 답변
9
6
더보기
Related knowledge
CakePHP 프로젝트 구성 CakePHP 프로젝트 구성 Sep 10, 2024 pm 05:25 PM

이번 장에서는 CakePHP의 환경 변수, 일반 구성, 데이터베이스 구성, 이메일 구성에 대해 알아봅니다.

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Dec 24, 2024 pm 04:42 PM

PHP 8.4는 상당한 양의 기능 중단 및 제거를 통해 몇 가지 새로운 기능, 보안 개선 및 성능 개선을 제공합니다. 이 가이드에서는 Ubuntu, Debian 또는 해당 파생 제품에서 PHP 8.4를 설치하거나 PHP 8.4로 업그레이드하는 방법을 설명합니다.

CakePHP 데이터베이스 작업 CakePHP 데이터베이스 작업 Sep 10, 2024 pm 05:25 PM

CakePHP에서 데이터베이스 작업은 매우 쉽습니다. 이번 장에서는 CRUD(생성, 읽기, 업데이트, 삭제) 작업을 이해하겠습니다.

CakePHP 날짜 및 시간 CakePHP 날짜 및 시간 Sep 10, 2024 pm 05:27 PM

cakephp4에서 날짜와 시간을 다루기 위해 사용 가능한 FrozenTime 클래스를 활용하겠습니다.

CakePHP 파일 업로드 CakePHP 파일 업로드 Sep 10, 2024 pm 05:27 PM

파일 업로드 작업을 위해 양식 도우미를 사용할 것입니다. 다음은 파일 업로드의 예입니다.

CakePHP 라우팅 CakePHP 라우팅 Sep 10, 2024 pm 05:25 PM

이번 장에서는 라우팅과 관련된 다음과 같은 주제를 학습하겠습니다.

CakePHP 토론 CakePHP 토론 Sep 10, 2024 pm 05:28 PM

CakePHP는 PHP용 오픈 소스 프레임워크입니다. 이는 애플리케이션을 훨씬 쉽게 개발, 배포 및 유지 관리할 수 있도록 하기 위한 것입니다. CakePHP는 강력하고 이해하기 쉬운 MVC와 유사한 아키텍처를 기반으로 합니다. 모델, 뷰 및 컨트롤러 gu

CakePHP 유효성 검사기 만들기 CakePHP 유효성 검사기 만들기 Sep 10, 2024 pm 05:26 PM

컨트롤러에 다음 두 줄을 추가하면 유효성 검사기를 만들 수 있습니다.

See all articles