PHP を使用していくつかの一般的な並べ替えアルゴリズム プログラムを作成する

並べ替えアルゴリズムはプログラミングで頻繁に使用されます。この記事では、PHP を使用していくつかの一般的な並べ替えアルゴリズムを実装します。

1. バブル ソート

バブル ソートは最も簡単に理解できますが、時間計算量 (O(n^2)) も最も大きいものの 1 つです。実装コードは次のとおりです。

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. 選択の並べ替え

選択の並べ替えは比較的理解しやすく、実装コードは次のとおりです:

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 . ヒル ソート

ヒル ソートは、実際には、挿入ソートの最適化されたバージョンとして理解できます。そのため、ヒル ソートは、配列によって異なります。その時間は複雑です。次数は O(nlogn) と O(n^2) の間です。実装コードは次のとおりです:

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));

5 ヒープ ソートは効率的です。ソートアルゴリズムの計算量は O(nlogn) です。原則は、まず配列を最大ヒープに変換し、次に最初の要素を i 番目の要素と交換し、次に残りの i-1 要素を最大ヒープに変換し、次に最初の要素を i 番目の要素と交換します。 1 つの要素が交換されます。実装コードは次のとおりです: function heapSort($arr) {

 $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));

6. Quick sort

Quick sort も効率的なソート アルゴリズムであり、その時間計算量も 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));

7. マージ ソート

マージ ソートの時間計算量も O(nlogn) です。原則は、2 つのソートされた配列の場合、2 つの配列をそれぞれ走査し、小さい要素を取得して新しい配列に挿入すると、新しい配列もソートされます。コードは次のとおりです。

function mergeSort($arr) {
 $len = count($arr);
 $arr = mergeSortRecursion($arr, 0, $len - 1);
 return $arr;
}
function mergeSortRecursion(&$arr, $begin, $end) {
 if ($begin < $end) {
  $mid = floor(($begin + $end) / 2);
  // 把数组不断拆分，只到只剩下一个元素，对于一个元素的数组，一定是排序好的
  mergeSortRecursion($arr, $begin, $mid);
  mergeSortRecursion($arr, $mid + 1, $end);
  $i = $begin;
  $j = $mid + 1;
  $k = 0;
  $temp = array();
  // 开始执行归并，遍历两个数组，从它们里面取较小的元素插入到新数组中
  while ($i <= $mid && $j <= $end) {
if ($arr[$i] < $arr[$j]) {
 $temp[$k++] = $arr[$i++];
} else {
 $temp[$k++] = $arr[$j++];
}
  }
  while ($i <= $mid) {
$temp[$k++] = $arr[$i++];
  }
  while ($j <= $end) {
$temp[$k++] = $arr[$j++];
  }
  for ($i = 0; $i < $k; $i++) {
$arr[$i + $begin] = $temp[$i];
  }
 }
 return $arr;
}
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

この記事では、並べ替えアルゴリズムを実装するための PHP プログラムの使用方法について詳しく説明します。関連コンテンツの詳細については、PHP 中国語 Web サイトを参照してください。

関連する推奨事項:

PHP は、それが AJAX リクエストであるかどうかをどのように判断しますか?

PHP プログラムによって報告される date() 警告を処理するための解決策

PHP 開発における同時実行の問題を解決する方法導入方法の事例発見

以上がPHP を使用していくつかの一般的な並べ替えアルゴリズム プログラムを作成するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。