PHP 정렬 알고리즘 시리즈의 삽입 정렬에 대한 자세한 설명-PHP 튜토리얼-php.cn

PHP 정렬 알고리즘 시리즈의 삽입 정렬에 대한 자세한 설명

jacklove

풀어 주다： 2023-04-02 10:14:02

원래의

1578명이 탐색했습니다.

이 글에서는 PHP 정렬 알고리즘 시리즈의 삽입 정렬 관련 정보를 주로 소개합니다. 관심 있는 친구들은

#🎜🎜을 참조하세요.

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

Principle

직접 삽입 정렬(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;
}

로그인 후 복사

알고리즘 시간 복잡도 계산

at In 최선의 경우(요소가 이미 순서대로 되어 있음): 그러면 n-1번만 반복하면 되며 시간 복잡도는 O(n)입니다.
최악의 경우(요소가 역순으로 되어 있음): Number 루프 조정 수: [n * (n-1) ] / 2, 시간 복잡도는 O (n ^ 2)
평균 시간 복잡도는 O (n ^ 2)

위 이 기사의 전체 내용이 모든 사람의 연구에 도움이 되기를 바랍니다. 또한 모든 사람이 PHP 중국어 웹사이트를 지원하기를 바랍니다.