PHP實現常見排序算法的示例代碼

1、冒泡排序

兩兩相比,每循環一輪就不用再比較最後一個元素瞭,因為最後一個元素已經是最大或者最小。

function maopaoSort ($list)
{
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($list[$j] > $list[$j + 1]) {
                $tmp = $list[$j];
                $list[$j] = $list[$j + 1];
                $list[$j + 1] = $tmp;
            }
        }
    }
    return $list;
}

2、選擇排序

選定一個作為基本值,剩下的和這個比較,然後調換位置。

function xuanzeSort ($list)
{
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        $pos = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($list[$pos] > $list[$j]) {
                $pos = $j;
            }
        }
        if ($pos != $i) {
            $tmp = $list[$pos];
            $list[$pos] = $list[$i];
            $list[$i] = $tmp;
        }
    }
    return $list;
}

3、快速排序

原理就是拿出一個標尺值,然後分為左右兩個數組,分別對比

function kuaisuSort ($list)
{
    $len = count($list);
    if ($len <= 1) {//遞歸出口
        return $list;
    }
    $base = $list[0];//選擇一個比較值
    $leftList = $rightList = [];
    for ($i = 1; $i < $len; $i++) {
        if ($base > $list[$i]) {
            $leftList[] = $list[$i];
        } else {
            $rightList[] = $list[$i];
        }
    }
    //遞歸分別再處理左右兩邊的數組
    $leftList = kuaisuSort($leftList);
    $rightList = kuaisuSort($rightList);
    return array_merge($leftList, [$base], $rightList);
}

4、插入排序

假設前面的數都是排好順序的,要把第n個數插入到有序裡

function charuSort ($list)
{
    $len = count($list);
    for ($i = 1; $i < $len; $i++) {
        $tmp = $list[$i];//獲取對比元素
        for ($j = $i - 1; $j > 0; $j--) {
            if ($list[$j] > $tmp) {
                $list[$j + 1] = $list[$j];
                $list[$j] = $tmp;
            } else {
                break;
            }
        }
    }
    return $list;
}

補充

當然PHP還能實現其他的常見排序算法,如歸並排序、希爾排序、堆排序等

歸並排序

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

堆排序

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

到此這篇關於PHP實現常見排序算法的示例代碼的文章就介紹到這瞭,更多相關PHP排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: