php 프로젝트 개발 에 사용 되 는 빠 른 정렬 알고리즘 분석
실제로 웹 개발 을 할 때 일부 알고리즘 을 사용 하 는 것 과 같은 것 을 자주 만 나 지 못 합 니 다.검색엔진 을 하 는 것 도 아니 고 바 텀 을 쓰 는 것 도 아 닙 니 다.(예 를 들 어 my sql 과 같은 데이터 베 이 스 를 쓰 는 것 은 스스로 정렬 알고리즘 을 실현 해 야 합 니 다)또한 모든 언어,예 를 들 어 자바,phop 은 어느 정도 정렬 함 수 를 프로그래머 에 게 사용 하도록 밀봉 되 어 있 습 니 다.예 를 들 어 공감 대가 있 습 니 다.여러분 이 웹 개발 을 하 는 기본 적 인 것 은 모두 알 고 있 습 니 다.업무 논리 가 많 고 간단 하 며 복잡 한 업무 논리 가 아 닙 니 다.우 리 는 웹 개발 의 프로그래머 로 서 기본적으로 웹 구조 이 고 데이터 베 이 스 를 삭제 하고 데 이 터 를 수정 한 다음 에 데 이 터 를 페이지 에 보 여 주 는 것 은 대부분이 성능 최적화,캐 시 등 과 관련된다.
흔히 볼 수 있 는 알고리즘 을 배 우 는 것 은 특수 한 응용 을 실현 하 는 데 도움 이 된다.예 를 들 어 우 리 는 데이터베이스 에 있 는 orderby 에 의존 하여 순 서 를 매 겼 기 때문에 데이터베이스 에 직접 연결 하여 순 서 를 매 기 는 것 에 매우 익숙 하 다.
그 다음 에 나 는 스스로 순 서 를 정 해 야 하 는 것 을 만 났 다.
우 리 는 실제 개발 에서 문제 에 부 딪 히 면 내 가 순 위 를 매 겨 야 하기 때문이다.요 구 는 다음 과 같 습 니 다.
상품 표 안에 한 필드 가 goods 입 니 다.price(상품 가격),지금 판 촉 가 기능 을 개발 하려 고 합 니 다.판 촉 가 는 시간 범위 가 설정 되 어 있다.프론트 페이지 에서 상품 을 전시 할 때.현재 시간 이 판 촉 시간 에 맞 으 면판 촉 가격 에 따라 집행 해 야 합 니 다.그래서 판 촉 가 는 따로 필드 를 추가 하여 보존 하 는데 promote 라 고 합 니 다.price,판 촉 시간 설정 정보,예 를 들 어 언제,매일 몇 시 부터 몇 시 까지 같은 시간 설정 정 보 는 잠시 상관 하지 않 습 니 다.다른 필드 에 저 장 된 것 은 전시 할 때 현재 시간 과 설정 시간 을 비교 해 야 합 니 다.
단일 상품 을 전시 할 때 는 판 촉 기간 내 여 부 를 직접 판단 하면 된다.정렬 에 문제 가 없습니다.
상품 목록 페이지 를 만 들 때 이런 작은 디 테 일 을 통 해 저 는 수 요 를 발견 할 수 있 습 니 다.사용 자 는 상품 가격 을'높 은 것 에서 낮은 것'으로 선택 할 수도 있 고'낮은 것 에서 높 은 것'으로 정렬 할 수도 있 습 니 다.
단순 정렬 이 라면 데이터베이스 에 직접 맡 겨 정렬 하 는 것 이 일반적 입 니 다.보통 sql 에서"order by goods"를 사용 하 는 것 에 익숙 합 니 다.price DESC'와 같은 문 구 는 가격 인하 또는 오름차 순 으로 진행 된다.
지금,goodsprice(상품 가격)순 서 는 ok.예 를 들 어 현재 시간 에 어떤 상품 은 판 촉 시간 에 부합 되 는 것 이 라면 판 촉 가격 도 정렬 해 야 한다.
간단 한 order by goodsprice DESC,promote_price DESC 라 는 방법 은 현재 의 수요 에 전혀 맞지 않 습 니 다.
그래서 데이터베이스 에 건 네 준 order by goodsprice DESC 는 한 번 정렬 하여 데 이 터 를 보 여 줍 니 다.
그리고 어떤 상품 데이터 가 판 촉 가격 에 부합 되 는 지 두루 살 펴 보 세 요.그리고 스스로 코드 를 만들어 정렬 합 니 다.
나의 초기 생각 은 현재 페이지 의 데 이 터 를 받 아서 각 줄 이 판 촉 가 시간 에 부합 되 는 지 판단 하 는 것 이다.
foreach( )
{
if ($v['promote_price'] > 0 && $promote_class->promtoe_validate($food_info)) {
$v['is_promote'] = true;
$v['price']= $v['promote_price'];
//
}
}
위의 목록 에 대해 서 는 위 목록 이 my sql 순 서 를 거 친 후에 판 촉 가 를 거 쳤 기 때 문 입 니 다.그래서 정렬 알고리즘 을 다시 만들어 정렬 해 야 합 니 다.이렇게 하면 판 촉 가격 이 낮은 것 을 앞 에 놓 을 수 있다.사실 my sql 데이터 베 이 스 는 c 언어 로 작 성 된 것 입 니 다.데이터베이스 orderby 를 이해 합 니 다.정렬 은 c 언어 로 배열 에 대한 정렬 을 실현 하 는 것 입 니 다.(관계 표 에서 돌아 오 는 줄 목록 은 2 차원 배열 입 니 다)
다만,평소에 우리 의 순 서 는 데이터베이스 에 맡 겨 이 루어 졌 다.스스로 작성 하 는 경 우 는 드 물기 때문에 접촉 이 많 지 않 기 때문에 이 알고리즘 들 은 자신 이 사용 할 수 없다 고 생각 합 니 다.지금도 phop 언어 로 데 이 터 를 정렬 해 야 합 니 다.
데이터베이스 의 order by a DESC,b ASC 실현 원리 추측?
첫 번 째 이해:먼저 a 필드 에 따라 정렬 합 니 다.그리고 데 이 터 를 b 필드 에 따라 정렬 합 니 다.
두 번 째 이해:먼저 a 필드 에 따라 정렬 하고 두 개의 값 이 같은 것 을 만나면 누가 앞 에 있 는 지 확인 할 수 없 을 때 b asc 를 사용 하여 두 데이터 의 우선 순 위 를 확인한다.
저 는 첫 번 째 이 해 였 습 니 다.나중에 바로 잡 았 습 니 다.두 번 째 이 해 는 맞 는 것 입 니 다.이것 이 디자인 의 고려 점 에 비교적 부합 되 기 때 문 입 니 다.
왜 여러 필드 로 정렬 할 수 있 도록 설계 해 야 합 니까?서 로 를 덮 기 위해 서인 가?예 를 들 어 a 필드 에 따라 정렬 했다.어떤 두 가지 데 이 터 는 원래 하 나 는 앞 에 있 고,또 b asc 에 따라 정렬 하면 원래 이 두 가지 데이터 의 순서 가 잘못 될 수 있 습 니 다.바로 뒤의 정렬 규칙 이 적 용 된 결 과 를 앞 에 덮어 쓸 수 있 습 니 다.
데이터베이스 정렬 이 이런 디자인 이 라 고 가정 하면 실제 적 인 의미 가 없다.여러 필드 를 디자인 하여 정렬 하 는 이유.바로 해결 하기 위해 서 두 줄 에서 a 필드 의 값 이 모두 2,2 일 때 어떻게 선 후 를 확정 합 니까?이 럴 때 뒤의 정렬 규칙 을 호출 하여 이 두 가지 데 이 터 를 정렬 합 니 다.그래서 order by 뒤의 필드 의 선후 순서 에 따라 효과 가 다 릅 니 다.
현실 생활 예:100 명의 학생 들 의 영어 성적 을 따 야 한다 고 가정 하고 순 위 를 정할 때 세 명의 학생 을 만나면 모두 88 점 이다.누가 상위 권 에 있 습 니까?이 럴 때 새로운 정렬 방식 을 추가 하여 이 세 학생 에 게 그들의 품행 을 보고 순 서 를 나 눌 수 있다.그 랬 으 면 좋 겠 다.확실 해.
인터넷 의 빠 른 정렬 법 은 모두 1 차원 배열 을 대상 으로 이 루어 진 것 이다.지금 나 는 데이터베이스 에 있 는 줄,즉 2 차원 배열 을 매개 변수 로 하고 임의의 필드 를 정렬 방식 으로 지정 할 수 있다.
예 를 들 어 데이터베이스 에서 데이터 목록 을 조회 하면 이 목록 에 대해 특정한 필드 를 지정 하여 정렬 할 수 있 습 니 다(데이터 베 이 스 는 바로 이 수 요 를 실현 하 는 것 입 니 다.물론 그들 이 먼저 들 어가 야 한다.그 는 허풍 을 좀 떨 었 다.
구체 적 으로 아래 를 보 세 요.
/*
* : , 。 ( , order by )
* +--------------------------------------------------------------------------
* @param $arr , 。 array(
* 0=>array(" 1"=>'',' 2'=>''...)
* 1=>array(" 1"=>'',' 2'=>''...)
* 2=>array(" 1"=>'',' 2'=>''...)
* )
* +--------------------------------------------------------------------------
* @param $key_field , 。
* +--------------------------------------------------------------------------
* @param $sort_type = asc or desc 。 ,
*/
function quickSort($arr, $key_field, $sort_type = "asc") {
if (count($arr) > 1) {
// , ,
$key_value_arr = array();
$return_arr = array();
//
foreach ($arr as $k => $v) {
$key_value_arr[$k] = $v[$key_field]; //
}
//php ,
if ($sort_type == 'desc') {
arsort($key_value_arr);
} else {
asort($key_value_arr);
}
reset($key_value_arr);
foreach ($key_value_arr as $k => $v) {
$return_arr[$k] = $arr[$k]; //
}
return $return_arr;
} else {
return $arr;
}
}
빠 른 정렬 법 에 대한 이 해 를 정리 해 보 겠 습 니 다.100 개의 요소 가 있다 고 가정 하고 정렬 합 니 다.그럼 몇 번 을 옮 겨 다 녀 야 하나 요?적어도 100 번 은 옮 겨 다 녀 야 한다.피 할 수 없 기 때문에 모든 요 소 를 하나씩 스 캔 해서 왼쪽 으로 던 질 까요,오른쪽 으로 던 질 까요?처음 분할 되면분할 후 양쪽 의 절 차 를 계속 반복 해 야 한다.
원소 의 수량 이 적 을 때 구별 을 느끼 지 못 한다.수량 이 많 으 면 수만 개의 원소 에 이른다.정렬 이 필요 하면 알고리즘 이 필요 합 니 다.
예 를 들 어 키 가 비교적 크 고 현실 적 인 상황 에서 우 리 는 눈 으로 어느 것 이 더 작은 지 보고 생각 하 는 순 서 를 정할 수 있다.하지만 컴퓨터 는 다르다.우 리 는 프로그램 을 만들어 서 그것 이 어떤 방법 으로 실현 되 어야 하 는 지 알려 야 한다.
빠 른 정렬 에 나타 난 사상 은 분 치 법 이다.작은 덩어리 로 나 누 어 하나씩 해결 하 다.
대체적인 사고 설명:
1.한 무더기 의 데이터 에서 기준 적 인 데 이 터 를 찾 습 니 다.이 데이터 표준 에 따라 분할 하 다.현실 적 인 예 로 한 무리의 사람들 이 100 명 으로 키 가 비교적 크다.지금 나 는 높이 의 사람 을 찾 아 냈 다.나 는 이 사람의 키 에 따라 a,b 두 조로 나 누 었 다.그 보다 작은 사람 은 모두 a 조 에 서 있 고,그 보다 큰 사람 은 모두 b(그 와 같은 높이 는 어느 쪽 에 놓 아 도 된다)에 서 있다.이렇게 하면 100 명 을 두 조로 나 눌 수 있다.
결 과 는 a 조 안의 모든 사람 이 키 가<=b 조 안의 사람 이다.
2.a 조 안에 있 는 사람 에 게 첫 번 째 단 계 를 반복 합 니 다.b 조 안의 사람들 에 게 도 첫 번 째 단 계 를 반복 한다.
3.마지막 에 하나 밖 에 남지 않 았 기 때문에(더 이상 자 를 수 없 기 때문에)조 를 나 누 었 습 니 다.
나 는 먼저 큰 덩어리 로 자 른 다음 에 모든 큰 덩어리 를 단독으로 처리 하 는 사상 을 배 웠 다.마지막 으로 각 블록의 처리 결 과 를 모두 합치다.
function quickSort($arr) {
if(count($arr) > 1) {
$k=$arr[0];
$x=array();
$y=array();
$_size=count($arr);
for($i=1;$i<$_size;$i++) {
if($arr[$i] <=$k) {
$x[] =$arr[$i];//
}else{
$y[] =$arr[$i];// 。 , , $x[] =$arr[$i];
}
}
//
$x= quickSort($x);// , ,
$y= quickSort($y);//
returnarray_merge($x,array($k),$y);
}else{
return$arr;
}
}
부정 확 한 점 은 지적 을 환영 합 니 다!코드 백업:
<?php
// : 。 key 。 。
/*
key key。 , 。 key。
:
array('1'=>'a','4'=>''b','3'=>'c','5'=>'d');
1,2,4 key ,
, sql :order by a,b,c
a , b 。 , c 。
*/
/*
$keys = array();
$keys['gg'] = '8.9';
$keys[1] = '8.8';
$keys[5] = '7.5';
asort($keys);// , key 。 。 key 。 ,0,1,2,3,4
reset($keys);
var_dump($keys);
*/
/*
* +-------------------------------------------------------
*
* @author wangtao 2015.6.10
* +-------------------------------------------------------
* @param $arr , 。
array(
* 0=>array(" 1"=>'',' 2'=>''...)
* 1=>array(" 1"=>'',' 2'=>''...)
* 2=>array(" 1"=>'',' 2'=>''...)
* )
* @param $key_field
* @param $sort_type = asc or desc 。 ,
* +-------------------------------------------------------
* return 。 key
* :1=>array(" 1"=>'',' 2'=>''...),2=>array(" 1"=>'',' 2'=>''...)
* " 2" ,key 2 , key ,
* +-------------------------------------------------------
*/
function quick_sort($arr, $key_field, $sort_type = "asc") {
if (count($arr) > 1) {
// , ,
$key_value_arr = array();
$return_arr = array();
// , ,
foreach ($arr as $k => $v) {
@ $key_value_arr[$k] = $v[$key_field]; //
}
//php ,
if ($sort_type == 'desc') {
arsort($key_value_arr);
} else {
asort($key_value_arr);
}
reset($key_value_arr);
foreach ($key_value_arr as $k => $v) {
$return_arr[$k] = $arr[$k]; //
}
//var_dump($return_arr);
return $return_arr;
} else {
return $arr;
}
}
$array = array(
array('name'=>' ','brand'=>' ','price'=>1050),
array('name'=>' ','brand'=>'lenovo','price'=>4300),
array('name'=>' ','brand'=>' ','price'=>3100),
array('name'=>' ','brand'=>' ','price'=>4900),
array('name'=>' ','brand'=>' ','price'=>960),
array('name'=>' ','brand'=>' ','price'=>6299),
array('name'=>' ','brand'=>' ','price'=>1200),
array('name'=>' ','brand'=>' ','price'=>1050),
);
var_dump(quickSort($array,'m'));
//
$row = array(
0=>null,
1=>null,
2=>null,
3=>null,
);
asort($row);
var_dump($row);// 。 key ?
/* array
3 => null
2 => null
1 => null
0 => null
, null, 。 。
*/
더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.,,,,,,,,,,,,,,,본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Laravel - 변환된 유효성 검사 규칙으로 API 요청 제공동적 콘텐츠를 위해 API를 통해 Laravel CMS에 연결하는 모바일 앱(또는 웹사이트) 구축을 고려하십시오. 이제 앱은 CMS에서 번역된 콘텐츠를 받을 것으로 예상되는 다국어 앱이 될 수 있습니다. 일반적으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.