PHP 정렬 알고리즘 의 힐 정렬(Shell Sort)실례 분석
기본 사상:
힐 정렬 이란 아래 표 시 된 일정한 증분 에 따라 그룹 을 나 누 어 각 그룹 에 대해 사용 하 는 것 을 말한다직접 삽입 정렬증 가 량 이 점점 줄 어 들 면서 각 그룹 에 포 함 된 키워드 가 점점 많아 지고 증 가 량 이 1 로 줄 어 들 때 전체 서열 이 마침 한 그룹 으로 나 뉘 어 알고리즘 이 종료 된다.
작업 단계:
n(시퀀스 기록 개수)보다 작은 정수 d1 을 첫 번 째 증분 으로 하고 파일 의 모든 기록 을 그룹 으로 나 눕 니 다.모든 거리 가 d1 인 배수 의 기록 은 같은 그룹 에 놓 여 있다.먼저 각 조 에서 진행 합 니 다직접 삽입 정렬;그 다음 에 두 번 째 증분 d2
이 방법 은 실질 적 으로 그룹 삽입 방법 이다.
원 거리(증분 이 라 고 함)의 수 를 비교 하여 득 수 를 이동 할 때 여러 요 소 를 뛰 어 넘 을 수 있 도록 한 번 비[2]를 하면 여러 요소 의 교환 을 없 앨 수 있다.D.L.셸 은 1959 년 그의 이름 을 딴 정렬 알고리즘 에서 이 사상 을 실현 했다.알고리즘 은 먼저 정렬 할 그룹의 수 를 특정한 증분 d 에 따라 여러 그룹 으로 나 누고 각 그룹 에 기 록 된 아래 표 차 이 는 d.각 그룹의 모든 요 소 를 정렬 한 다음 에 작은 증분 으로 이 를 진행 하여 각 그룹 에서 정렬 합 니 다.증 량 이 1 로 줄 어 들 면 전체 정렬 할 수 는 한 그룹 으로 나 뉘 어 정렬 이 완 료 됩 니 다.
일반적인 첫 번 째 추출 서열 의 절반 은 증 가 량 이 고,이후 에는 매번 반 으로 줄 어 증 가 량 이 1 이 될 때 까지 한다.
증 량 의 취 법 에 대해 서 는 지금까지 가장 좋 은 증 량 서열 을 찾 지 못 했다 고 한다.그러나 마지막 증 량 치 는 반드시 1 이 어야 한 다 는 강 한 요구 가 있다.
주어진 인 스 턴 스 셸 정렬 과정
정렬 대기 파일 에 10 개의 기록 이 있다 고 가정 하면 키 워드 는 다음 과 같 습 니 다.
49，38，65，97，76，13，27，49，55，04。
증분 시퀀스 의 값 은 다음 과 같 습 니 다.
5，3，1
알고리즘 구현:
<?php
// ( )
function ShellSort(array &$arr)
{
$count = count($arr);
$inc = $count; //
do {
//
//$inc = floor($inc / 3) + 1;
$inc = ceil($inc / 2);
for ($i = $inc; $i < $count; $i++) {
$temp = $arr[$i]; //
// $temp
for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
$arr[$j + $inc] = $arr[$j]; //
}
//
$arr[$j + $inc] = $temp;
}
// 1
} while ($inc > 1);
}
//$arr = array(9,1,5,8,3,7,4,6,2);
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);
array(10) {
[0]=>
int(4)
[1]=>
int(13)
[2]=>
int(27)
[3]=>
int(38)
[4]=>
int(49)
[5]=>
int(49)
[6]=>
int(55)
[7]=>
int(65)
[8]=>
int(76)
[9]=>
int(97)
}
상기 코드 의 분석 을 통 해 힐 정렬 의 관건 은 마음대로 그룹 을 나 눈 후에 각자 정렬 하 는 것 이 아니 라 특정한'증 량'의 기록 을 하나의 하위 서열 로 구성 하여 점프 식 이동 을 실현 하여 정렬 의 효율 을 높 인 다 는 것 을 잘 알 고 있 을 것 이 라 고 믿 습 니 다.
최 악의 경우 시간 복잡 도 는 O(n^2)입 니 다.
힐 정렬 은 불안정 정렬 입 니 다.
본 고 는 을 참고 하여 여기 서 기록 만 하고 나중에 조회 하기에 편리 하 며 큰 신 은 뿌리 지 마 세 요!
PS:정렬 에 관 한 프 리 젠 테 이 션 도 구 를 추천 합 니 다.참고 하 시기 바 랍 니 다.
온라인 애니메이션 프레젠테이션 삽입/선택/거품/병합/힐/빠 른 정렬 알고리즘 프로 세 스 도구:
대화 데이터 구조
더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
laravel에 yo에서 angularJs&coffeescript를 사용할 수 있도록 한다.먼저 yo 명령을 사용할 수 있어야하므로 아래에서 설치 global에 설치한 곳에서 laravel의 프로젝트 루트로 이동. 클라이언트 코드를 관리하는 디렉토리를 만들고 이동합니다. 클라이언트 환경 만들기 이것으로 히...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
