php 프로젝트 개발 에 사용 되 는 빠 른 정렬 알고리즘 분석

11262 단어 php빠 른 정렬
본 고 는 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 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.

좋은 웹페이지 즐겨찾기