PHP數組排序算法實現(14種)

aisuhua 發布于2019-06-27 13:54 / 2528人閱讀

摘要：本文將介紹快速排序計數排序梳排序堆排序歸并排序希爾排序選擇排序插入排序地精排序聯合冒泡排序雞尾酒排序冒泡排序奇偶排序使用標志的冒泡排序種排序算法的實現。是一種不穩定的排序算法。

本文將介紹快速排序、計數排序、梳排序、堆排序、歸并排序、希爾排序、選擇排序、插入排序、地精排序、聯合冒泡排序、雞尾酒排序、冒泡排序、奇偶排序、使用標志的冒泡排序14種排序算法的實現。本文是由于閱讀了文章《測試評估：14種排序算法和PHP數組》，才有想法學習、實現并總結這些算法，特此分享，陸續補充。

快速排序

1、思想：主要采用了遞歸和分治的思想。選擇標尺后，進行遍歷數組，將大于標尺的放到一個數組，將小于標尺的放置到一個數組。再遞歸調用本函數并記錄結果。

2、實現

function quickSort($arr) {
        //先判斷是否需要繼續進行
        $length = count($arr);
        if($length <= 1) {return $arr;}

        //選擇一個標尺,通常選擇第一個元素
        $base_num = $arr[0];

        //初始化
        $left = array();//小于標尺的
        $right = array();//大于標尺的

        for($i=1;$i<$length;$i++) {
            if($base_num > $arr[$i]) {
                $left[] = $arr[$i];
            }else {
                $right[] = $arr[$i];
            }
        }

        //遞歸調用并記錄
        $left = $this->quickSort($left);
        $right = $this->quickSort($right);

        //合并
        return array_merge($left,array($base_num), $right);

3、輸入$arr = array(12, 100, 3, 20, 11,50);

4、輸出

array:6 [▼
  0 => 3
  1 => 11
  2 => 12
  3 => 20
  4 => 50
  5 => 100
]

計數排序

1、此算法，是一種穩定的線性時間排序算法。其基本思想是，用待排序的數作為計數數組的下標，統計每個數字的個數。然后依次輸出即可得到有序序列。但是理解比較難，本人還沒理解通透，但是總結了幾個步驟：

找出數組$arr中最大的數$max

初始化用來計數的數組$count_arr，數組大小為$max

對于計數數組$count_arr鍵值等于$arr[$i]的值加1

計數數組$count_arr相鄰的兩個值相加

鍵值翻轉得到數組$over_turn

loop$over_turn，按照順序push到最終的數組$result

2、實現

function countingSort($arr) {

        $length = count($arr);
        if($length <= 1) return $arr;

        $size = count($arr);
        $max = $arr[0];

        //找出數組中最大的數
        for($i=1;$i<$size;$i++) {
            if($max < $arr[$i]) $max = $arr[$i];
        }

        //初始化用來計數的數組
        for ($i=0;$i<=$max;$i++) {
            $count_arr[$i] = 0;
        }

        //對計數數組中鍵值等于$arr[$i]的加1
        for($i=0;$i<$size;$i++) {
            $count_arr[$arr[$i]]++;
        }

        //相鄰的兩個值相加
        for($i=1;$i<=$max;$i++) {
            $count_arr[$i] = $count_arr[$i-1] + $count_arr[$i];
        }

        //鍵與值翻轉
        for ($i=$size-1;$i>=0;$i--) {
            $over_turn[$count_arr[$arr[$i]]] = $arr[$i];
            $count_arr[$arr[$i]]--; // 前一個數找到位置后，那么和它值相同的數位置往前一步
        }

        //按照順序排列
        $result = array();
        for ($i=1;$i<=$size;$i++) {
            array_push($result,$over_turn[$i]);
        }

        return $result;
    }

3、輸入$arr = array(8,6,1,3,4)

4、輸出

array:5 [▼
  0 => 1
  1 => 3
  2 => 4
  3 => 6
  4 => 8
]

梳排序

1、思想：梳排序同樣基于冒泡排序，梳排序比較的是固定距離處的數的比較和交換,類似希爾那樣。是一種不穩定的排序算法。

2、實現

function combSort($arr) {
    $length = count($arr);
    $step = (int)floor($length/1.3);
    while($step >= 1) {
        for($i=0;$i<$length;$i++) {

            if($i+$step<$length && $arr[$i]>$arr[$i+$step]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i+$step];
                $arr[$i+$step] = $temp;
            }

            if($i+$step>$length) {
                break;
            }

        }
        $step = (int)floor($step/1.3);
    }
        return $arr;
    }

3、輸入$arr = array(8,4,3,7,6,5,2,1)

4、輸出

array:8 [▼
  0 => 1
  1 => 2
  2 => 3
  3 => 4
  4 => 5
  5 => 6
  6 => 7
  7 => 8
]

待補充

參考文章
測試評估：14種排序算法和PHP數組：http://blog.jobbole.com/68774/

云服務器 GPU云服務器 java三種排序算法字符串排序數組排序算法數組排序算法c語言 php 四種排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/21682.html

PHP 計數排序

摘要：計數排序不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。計數排序不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。算法描述找出待排序的數組中最大和最小的元素；...

孫吉亮 2019-07-01 10:25 評論0 收藏0
PHP面試：常見查找算法一篇說透

摘要：我們現在來看二分搜索算法的兩種變形插值搜索和指數搜索。插值搜索是對二分搜索算法的改進，插值搜索可以基于搜索的值選擇到達不同的位置。預警在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復雜度。因為力求通俗易懂，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點理解一點。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。開篇和排序類似，搜索或者叫做...

付永剛 2019-07-01 10:47 評論0 收藏0
php 經典排序算法（解析）

摘要：介紹三種排序算法快速排序選擇排序冒泡排序選擇排序選擇排序是一種簡單直觀的排序算法。介紹三種排序算法快速排序選擇排序冒泡排序選擇排序選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。選擇排序是不穩定的排序方法（比如序列[5， 5， 3...

FuisonDesign 2019-06-28 14:08 評論0 收藏0
[討論]php 排序系列的函數內部的C實現是用了哪種排序算法？

摘要：在算法中，比快速排序還快的，無疑是基數排序，粗略看了一下算法，可能是基礎排序中的桶排序。桶排序是穩定的桶排序是常見排序里最快的一種，比快排還要快大多數情況下桶排序非常快，但是同時也非常耗空間以空間換時間 ext/standard/php_array.h https://github.com/php/php-src/blob/master/ext/standard/php_array....

chanthuang 2019-06-27 10:27 評論0 收藏0
JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0