집 > 기사 > 백엔드 개발 > PHP 정렬 알고리즘 시리즈 삽입 정렬 예제 공유

PHP 정렬 알고리즘 시리즈 삽입 정렬 예제 공유

小云云원래의: 2018-01-08 10:14:311540검색

이 글은 주로 PHP 정렬 알고리즘 시리즈의 삽입 정렬 관련 정보를 모두에게 자세히 소개합니다. 관심 있는 친구들이 참고하면 도움이 될 것입니다.

삽입 정렬

이미 정렬된 데이터 시퀀스가 있고, 이미 정렬된 데이터 시퀀스에 숫자를 삽입해야 하는데, 이 경우 삽입 후에도 데이터 시퀀스가 계속 정렬되어 있어야 합니다. 숫자를 사용하는 새로운 정렬 방법 - 삽입 정렬의 기본 작업은 이미 정렬된 데이터에 데이터를 삽입하여 숫자에 1을 더한 새로운 데이터를 얻는 것입니다. 이 알고리즘은 소량에 적합합니다. 데이터 정렬의 시간 복잡도는 O(n^2)입니다. 안정적인 정렬 방법입니다. 삽입 알고리즘은 정렬할 배열을 두 부분으로 나눕니다. 첫 번째 부분에는 마지막 요소를 제외한 배열의 모든 요소가 포함되며(배열에 삽입 위치를 확보할 수 있는 공간이 하나 더 추가됨) 두 번째 부분에는 이 요소만 포함됩니다. 요소(즉, 삽입할 요소)입니다. 첫 번째 부분이 정렬된 후 이 마지막 요소가 정렬된 첫 번째 부분에 삽입됩니다.

원리

직접 삽입 정렬(Insertion Sort)의 기본 아이디어는 정렬할 레코드가 키 크기에 따라 이전에 정렬된 하위 시퀀스의 적절한 위치에 삽입될 때마다 레코드까지 모두 삽입된다는 것입니다. 삽입이 완료되었습니다.
배열이 [0…n-1]이라고 가정합니다.

1. 처음에는 a[0]이 순서화된 영역을 형성하고 순서가 지정되지 않은 영역은 [1..n-1]입니다. i=1
2이라고 합니다. a[i]를 현재 정렬된 영역 a[0...i-1]에 병합하여 a[0...i]의 정렬된 간격을 형성합니다.
3.i++ i==n-1이 될 때까지 두 번째 단계를 반복합니다. 정렬이 완료되었습니다.

PHP 코드 구현

function insertSort($arr){
  //获取需要排序的长度
  $length=count($arr);
  //假定第一个为有序的，所以从$i开始比较
  for ($i=1; $i <$length ; $i++) {
    //存放待比较的值
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      //若插入值比较小，则将后面的元素后移一位，并将值插入
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

알고리즘 시간 복잡도 계산

최상의 경우(요소가 정렬된 경우): n-1번만 반복하면 되며 시간 복잡도는 O(n )
최악의 경우(요소는 역순): 루프 조정 횟수: [n * (n-1) ] / 2, 시간 복잡도는 O (n ^ 2)
평균 시간 복잡도는: O ( n^2)

PHP 정렬 알고리즘 시리즈 삽입 정렬 예제 공유

관련 기사