PHP를 사용하여 몇 가지 일반적인 정렬 알고리즘 프로그램 작성

정렬 알고리즘은 프로그래밍에서 자주 접하게 됩니다. 이 기사에서는 PHP를 통해 몇 가지 일반적인 정렬 알고리즘을 구현합니다.

1. 버블 정렬

버블 정렬은 이해하기 가장 간단하지만, 시간 복잡도(O(n^2))도 가장 큰 것 중 하나입니다. 구현 코드는 다음과 같습니다.

function bubbleSort($arr) {
 $len = count($arr);
 for ($i = 0; $i < $len; $i++) {
  // 遍历i后面的元素，只要该元素小于当前元素，就把较小的往前冒泡
  for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$i] > $arr[$j]) {
 $t = $arr[$i];
 $arr[$i] = $arr[$j];
 $arr[$j] = $t;
}
  }
 }
 return $arr;
}
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

2. 선택 정렬

선택 정렬은 비교적 이해하기 쉽고, 시간 복잡도도 O(n^2)입니다. 구현 코드는 다음과 같습니다.

function selectSort($arr) {
 $len = count($arr);
 for ($i = 0; $i < $len; $i++) {
  $minIndex = $i;
  // 找出i后面最小的元素与当前元素交换
  for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
 $minIndex = $j;
}
  }
  if ($minIndex != $i) {
$t = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $t;
  }
 }
 return $arr;
}
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

3. 삽입 정렬

삽입 정렬은 버블 정렬과 약간 비슷하다고 생각합니다. , 시간 복잡도도 O(n^2) )이므로 구현 코드는 다음과 같습니다.

function insertSort($arr) {
 $len = count($arr);
 for ($i = 1; $i < $len; $i++) {
  if ($arr[$i] < $arr[$i - 1]) {
$t = $arr[$i];
$j = $i - 1;
// 如果当前元素大于前一个元素，就往前挪
while ($j >= 0 && $t < $arr[$j]) {
 $arr[$j + 1] = $arr[$j];
 $j--;
}
$arr[$j + 1] = $t;
  }
 }
 return $arr;
}
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

4. Hill 정렬

Hill 정렬은 실제로 삽입 정렬의 최적화된 버전으로 이해될 수 있습니다. 증가량이 얼마나 필요한지는 배열에 따라 다르므로 Hill 정렬의 시간 복잡도는 O(nlogn)과 O(n^2)입니다. 5. 힙 정렬

힙 정렬은 시간 복잡도가 O(nlogn)인 효율적인 정렬 알고리즘입니다. 원칙은 먼저 배열을 최대 힙으로 변환한 다음 첫 번째 요소를 i번째 요소와 교환하고 나머지 i-1 요소를 최대 힙으로 변환한 다음 첫 번째 요소를 i번째 요소와 교환하는 것입니다. . 1개 요소가 교환됩니다. 구현 코드는 다음과 같습니다. function heapSort($arr) {

function shellSort($arr) {
 $len = count($arr);
 $stepSize = floor($len / 2);
 while ($stepSize >= 1) {
  for ($i = $stepSize; $i < $len; $i++) {
if ($arr[$i] < $arr[$i - $stepSize]) {
 $t = $arr[$i];
 $j = $i - $stepSize;
 while ($j >= 0 && $t < $arr[$j]) {
  $arr[$j + $stepSize] = $arr[$j];
  $j -= $stepSize;
 }
 $arr[$j + $stepSize] = $t;
}
  }
  // 缩小步长，再进行插入排序
  $stepSize = floor($stepSize / 2);
 }
 return $arr;
}
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

6. Quick sort

Quick sort도 효율적인 정렬 알고리즘이며, 시간 복잡도도 O(nlogn)입니다. 원칙은 기본 요소를 선택한 다음 배열에서 이 요소보다 작은 요소를 기본 요소 왼쪽에 배치하고, 그보다 큰 요소는 기본 요소 오른쪽에 배치하는 것입니다. 그런 다음 양쪽에서 동일한 작업을 계속하십시오. 코드는 다음과 같습니다.

 $len = count($arr);
 // 先建立最大堆
 for ($i = floor(($len - 1) / 2); $i >= 0; $i--) {
  $s = $i;
  $childIndex = $s * 2 + 1;
  while ($childIndex < $len) {
// 在父、左子、右子中 ，找到最大的
if ($childIndex + 1 < $len && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;
if ($arr[$s] < $arr[$childIndex]) {
 $t = $arr[$s];
 $arr[$s] = $arr[$childIndex];
 $arr[$childIndex] = $t;
 $s = $childIndex;
 $childIndex = $childIndex * 2 + 1;
} else {
 break;
}
  }
 }
 // 从最后一个元素开始调整
 for ($i = $len - 1; $i > 0; $i--) {
  $t = $arr[$i];
  $arr[$i] = $arr[0];
  $arr[0] = $t;
  // 调整第一个元素
  $s = 0;
  $childIndex = 1;
  while ($childIndex < $i) {
// 在父、左子、右子中 ，找到最大的
if ($childIndex + 1 < $i && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;
if ($arr[$s] < $arr[$childIndex]) {
 $t = $arr[$s];
 $arr[$s] = $arr[$childIndex];
 $arr[$childIndex] = $t;
 $s = $childIndex;
 $childIndex = $childIndex * 2 + 1;
} else {
 break;
}
  }
 }
 return $arr;
} 
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

7. 병합 정렬

병합 정렬의 시간 복잡도도 O(nlogn)입니다. 원칙은 두 개의 정렬된 배열의 경우 두 배열을 각각 순회하고 더 작은 요소를 가져와 새 배열에 삽입하면 새 배열도 정렬된다는 것입니다. 코드는 다음과 같습니다.

function quickSort($arr) {
 $len = count($arr);
 quickSortRecursion($arr, 0, $len - 1);
 return $arr;
}
 
function quickSortRecursion(&$arr, $begin, $end) {
 if ($begin < $end) {
  $left = $begin;
  $right = $end;
  $temp = $arr[$begin];// $temp为基准元素
  // 把小于$temp的元素放到$temp左边，大于它的放在右边
  while ($left < $right) {
while ($left < $right && $arr[$right] >= $temp) $right--;
if ($left < $right) {
 $arr[$left++] = $arr[$right];
}
while ($left < $right && $arr[$left] <= $temp) $left++;
if ($left < $right) {
 $arr[$right--] = $arr[$left];
}
  }
  $arr[$left] = $temp;
  // 把数组分成两部分，递归调用该函数
  quickSortRecursion($arr, $begin, $left - 1);
  quickSortRecursion($arr, $left + 1, $end);
 }
 return $arr;
}
 
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

이 글에서는 PHP 프로그램을 사용하여 정렬 알고리즘을 구현하는 방법을 자세히 설명합니다. 더 많은 관련 내용을 보려면 PHP 중국어 웹사이트를 참고하세요.

관련 권장 사항:

PHP는 AJAX 요청인지 여부를 어떻게 결정합니까?

PHP 프로그램에서 보고된 date() 경고에 대한 솔루션

PHP 개발 시 동시성 문제를 해결하기 위한 여러 구현 방법 사례 발견

위 내용은 PHP를 사용하여 몇 가지 일반적인 정렬 알고리즘 프로그램 작성의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!