Verwenden Sie PHP, um mehrere gängige Sortieralgorithmusprogramme zu schreiben-PHP-Tutorial-php.cn

Verwenden Sie PHP, um mehrere gängige Sortieralgorithmusprogramme zu schreiben

jacklove

Freigeben： 2023-03-30 16:10:02

Original

1594 Leute haben es durchsucht

Sortieralgorithmen kommen in der Programmierung häufig vor. In diesem Artikel werden mehrere gängige Sortieralgorithmen mithilfe von PHP implementiert.

1. Blasensortierung

Die Blasensortierung ist am einfachsten zu verstehen, aber ihre zeitliche Komplexität (O(n^2)) ist auch eine der größten. Der Implementierungscode lautet wie folgt:

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

Nach dem Login kopieren

2. Auswahlsortierung

Die Auswahlsortierung ist relativ einfach zu verstehen und ihre zeitliche Komplexität beträgt O(n^2). Der Implementierungscode lautet wie folgt:

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

Nach dem Login kopieren

3. Einfügungssortierung

Ich habe das Gefühl, dass die Einfügungssortierung der Blasensortierung etwas ähnelt und die zeitliche Komplexität ebenfalls O(n^2) ist. Der Implementierungscode lautet wie folgt:

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

Nach dem Login kopieren

4. Hill-Sortierung

Hill-Sortierung kann tatsächlich als optimierte Version der Einfügesortierung verstanden werden. Ihre Effizienz hängt vom Inkrement ab. Daher ist die Hill-Sortierung ein instabiler Sortieralgorithmus und seine Zeit ist komplex. Der Implementierungscode lautet wie folgt:

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

Nach dem Login kopieren

Heap-Sortierung ist ein Effizienter Sortieralgorithmus. Seine Zeit. Die Komplexität beträgt O(nlogn). Das Prinzip lautet: Konvertieren Sie zuerst das Array in einen maximalen Heap, tauschen Sie dann das erste Element gegen das i-te Element aus, konvertieren Sie dann die verbleibenden i-1 Elemente in einen maximalen Heap und tauschen Sie dann das erste Element gegen das i-te Element aus . 1 Element wird ausgetauscht und so weiter. Der Implementierungscode lautet wie folgt: Funktion 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));

Nach dem Login kopieren

6. Schnelle Sortierung

Schnelle Sortierung ist ebenfalls ein effizienter Sortieralgorithmus und seine zeitliche Komplexität beträgt ebenfalls O(nlogn). . Das Prinzip lautet: Wählen Sie ein Basiselement aus und platzieren Sie dann die Elemente im Array, die kleiner als dieses Element sind, links vom Basiselement, und die Elemente, die größer sind als dieses, werden rechts vom Basiselement platziert. Anschließend den gleichen Vorgang auf beiden Seiten fortsetzen. Der Code lautet wie folgt:

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

Nach dem Login kopieren

7. Zusammenführungssortierung

Die zeitliche Komplexität der Zusammenführungssortierung beträgt ebenfalls O(nlogn). Das Prinzip lautet: Durchlaufen Sie für zwei sortierte Arrays jeweils die beiden Arrays, erhalten Sie die kleineren Elemente und fügen Sie sie in das neue Array ein. Anschließend wird auch das neue Array sortiert. Der Code lautet wie folgt:

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

Nach dem Login kopieren

Dieser Artikel erläutert ausführlich die Verwendung von PHP-Programmen zur Implementierung des Sortieralgorithmus. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

Wie stellt PHP fest, ob es sich um eine AJAX-Anfrage handelt?

Lösungen für die date()-Warnung, die vom PHP-Programm gemeldet wird

So lösen Sie Parallelitätsprobleme in der PHP-Entwicklung Fallerkennung von Implementierungsmethoden

Das obige ist der detaillierte Inhalt vonVerwenden Sie PHP, um mehrere gängige Sortieralgorithmusprogramme zu schreiben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!