PHP實現(xiàn)常用排序算法的方法

function quickSort($arr)
 {
 $len = count($arr); 
 // 先設(shè)定結(jié)束條件，判斷是否需要繼續(xù)進行
 if($len = 1) {
 return $arr;
 } 
 
 // 選擇第一個元素作為基準(zhǔn)元素
 $pivot = $arr[0]; 
 
 // 初始化左數(shù)組
 $left = $right = array(); 
 
// 初始化大于基準(zhǔn)元素的右數(shù)組
 $right = array(); 
 
 // 遍歷除基準(zhǔn)元素外的所有元素，按照大小關(guān)系放入左右數(shù)組內(nèi)
 for ($i = 1; $i  $len ; $i++) {
 if ($arr[$i]  $pivot) {
 $left[] = $arr[$i];
 } else {
 $right[] = $arr[$i];
 }
 } 
 
 // 再分別對左右數(shù)組進行相同的排序
 $left = quickSort($left);
 $right = quickSort($right); 
 
 // 合并基準(zhǔn)元素和左右數(shù)組
 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);
 }
 } 

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

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

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

/**
 * 歸并排序
 *
 * @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;
 }

/**
 * 堆排序
 *
 * @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);
 }
 }

/**
 * 希爾排序 標(biāo)準(zhǔn)
 *
 * @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;
 }

/**
 * 基數(shù)排序
 *
 * @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;
 }