1.快速排序
function quickSort($arr) { $len = count($arr); // 先设定结束条件,判断是否需要继续进行 if($len <= 1) { return $arr; } // 选择第一个元素作为基准元素 $pivot = $arr[0]; // 初始化左数组 $left = $right = array(); // 初始化大于基准元素的右数组 $right = array(); // 遍历除基准元素外的所有元素,按照大小关系放入左右数组内 for ($i = 1; $i < $len ; $i++) { if ($arr[$i] < $pivot) { $left[] = $arr[$i]; } else { $right[] = $arr[$i]; } } // 再分别对左右数组进行相同的排序 $left = quickSort($left); $right = quickSort($right); // 合并基准元素和左右数组 return array_merge($left, array($pivot), $right); }
原地排序版本,不需要额外的存储空间:
function partition(&$arr, $leftIndex, $rightIndex) { $pivot = $arr[($leftIndex + $rightIndex) / 2]; while ($leftIndex <= $rightIndex) { while ($arr[$leftIndex] < $pivot) { $leftIndex++; } while ($arr[$rightIndex] > $pivot) { $rightIndex--; } if ($leftIndex <= $rightIndex) { list($arr[$leftIndex], $arr[$rightIndex]) = [$arr[$rightIndex], $arr[$leftIndex]]; $leftIndex++; $rightIndex--; } } return $leftIndex; } function quickSort(&$arr, $leftIndex, $rightIndex) { if ($leftIndex < $rightIndex) { $index = partition($arr, $leftIndex, $rightIndex); quickSort($arr, $leftIndex, $index - 1); quickSort($arr, $index, $rightIndex); } }
2.冒泡排序
function bubbleSort($arr) { $len = count($arr); for($i = 1; $i < $len; $i++) { for($k = 0; $k < $len - $i; $k++) { if($arr[$k] > $arr[$k + 1]) { $tmp = $arr[$k + 1]; $arr[$k + 1] = $arr[$k]; $arr[$k] = $tmp; } } } return $arr; }
3.插入排序
function insertSort($arr) { $len = count($arr); for ($i = 1; $i < $len; $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; }
4.选择排序
function selectSort($arr) { $len = count($arr); for ($i = 0; $i < $len; $i++) { $p = $i; for ($j = $i + 1; $j < $len; $j++) { if ($arr[$p] > $arr[$j]) { $p = $j; } } $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } return $arr; }
5.归并排序
/** * 归并排序 * * @param array $lists * @return array */ function merge_sort(array $lists) { $n = count($lists); if ($n <= 1) { return $lists; } $left = merge_sort(array_slice($lists, 0, floor($n / 2))); $right = merge_sort(array_slice($lists, floor($n / 2))); $lists = merge($left, $right); return $lists; } function merge(array $left, array $right) { $lists = []; $i = $j = 0; while ($i < count($left) && $j < count($right)) { if ($left[$i] < $right[$j]) { $lists[] = $left[$i]; $i++; } else { $lists[] = $right[$j]; $j++; } } $lists = array_merge($lists, array_slice($left, $i)); $lists = array_merge($lists, array_slice($right, $j)); return $lists; }
6.堆排序
/** * 堆排序 * * @param array $lists * @return array */ function heap_sort(array $lists) { $n = count($lists); build_heap($lists); while (--$n) { $val = $lists[0]; $lists[0] = $lists[$n]; $lists[$n] = $val; heap_adjust($lists, 0, $n); //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL; } return $lists; } function build_heap(array &$lists) { $n = count($lists) - 1; for ($i = floor(($n - 1) / 2); $i >= 0; $i--) { heap_adjust($lists, $i, $n + 1); //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL; } //echo "build ok: " . implode(', ', $lists) . PHP_EOL; } function heap_adjust(array &$lists, $i, $num) { if ($i > $num / 2) { return; } $key = $i; $leftChild = $i * 2 + 1; $rightChild = $i * 2 + 2; if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) { $key = $leftChild; } if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) { $key = $rightChild; } if ($key != $i) { $val = $lists[$i]; $lists[$i] = $lists[$key]; $lists[$key] = $val; heap_adjust($lists, $key, $num); } }
7.希尔排序
/** * 希尔排序 标准 * * @param array $lists * @return array */ function shell_sort(array $lists) { $n = count($lists); $step = 2; $gap = intval($n / $step); while ($gap > 0) { for ($gi = 0; $gi < $gap; $gi++) { for ($i = $gi; $i < $n; $i += $gap) { $key = $lists[$i]; for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) { $lists[$j + $gap] = $lists[$j]; $lists[$j] = $key; } } } $gap = intval($gap / $step); } return $lists; }
8.基数排序
/** * 基数排序 * * @param array $lists * @return array */ function radix_sort(array $lists) { $radix = 10; $max = max($lists); $k = ceil(log($max, $radix)); if ($max == pow($radix, $k)) { $k++; } for ($i = 1; $i <= $k; $i++) { $newLists = array_fill(0, $radix, []); for ($j = 0; $j < count($lists); $j++) { $key = $lists[$j] / pow($radix, $i - 1) % $radix; $newLists[$key][] = $lists[$j]; } $lists = []; for ($j = 0; $j < $radix; $j++) { $lists = array_merge($lists, $newLists[$j]); } } return $lists; }
原文链接:https://blog.csdn.net/l754539910/article/details/87635192