PHP 排序演算法原理及總結

2020-07-16 10:05:53
氣泡排序原理

原理描述:

一次比較倆個相鄰的元素,大的元素後移,小的元素前移(交換位置)。直到找出最大的元素。就像是氣泡一樣,大的向下沉,小的向上冒。

流程:

有一個無序陣列 $arr = [8, 9, 3, 6, 1, 4]

第一次外迴圈 :找出最大值 9,要倆倆相比,比 5 次。
8 9 3 6 1 4 第一次, 8 跟 9 比,9 大,所以沒有交換位置。
8 3 9 6 1 4 第二次, 9 跟 3 比, 9 大,交換位置。
8 3 6 9 1 4 第三次, 9 跟 6 比, 9 大,交換位置。
8 3 6 1 9 4 第四次, 9 跟 1 比, 9 大,交換位置。
8 3 6 1 4 9 第五次, 9 跟 4 比, 9 大,交換位置。
第二次外迴圈:找出第二大值 8,要倆倆相比,比 4 次。因為上一步已經找到最大值了。
3 8 6 1 4 9 第一次,8 跟 3 比,8 大, 交換位置。
3 6 8 1 4 9 第二次,8 跟 6 比,8 大, 交換位置。
3 6 1 8 4 9 第三次,8 跟 1 比,8 大, 交換位置。
3 6 1 4 8 9 第四次,8 跟 4 比,8 大, 交換位置。
第三次外迴圈:找出第三大的值 6,要倆倆相比,比三次。
3 6 1 4 8 9 第一次,3 跟 6 比,6 大,位置沒有變化。
3 1 6 4 8 9 第二次,6 跟 1 比,6 大,交換位置。
3 1 4 6 8 9 第三次,6 跟 4 比,6 大,交換位置。
第四次外迴圈:找出第四大的值 4,要倆倆相比,比 2 次。
1 3 4 6 8 9 第一次, 3 跟 1 比, 3 大,交換位置。
1 3 4 6 8 9 第二次, 3 跟 4 比, 4 大,位置不變。
第五次外迴圈:找出第五大的值 3, 比一次就夠了。
1 3 4 6 8 9 比一次。1 跟 3 比,3 大,位置沒有變化。

總結:

1. 外層迴圈要元素數 - 1次。負責找出最大值。

2. 內層迴圈逐層遞減一次。負責倆倆相比較,交換元素位置。

程式碼:

<?php
        function bubbleSort($arr) 
        {
            $len = count($arr);//獲取元素個數
            for ($i = 0; $i < $len - 1; $i ++) {//找出最大值
                $flag = 0;//做一個標記
                for($j = 0; $j < $len - 1 - $i; $j++) {//倆倆相比較,交換位置
                    if ($arr[$j] > $arr[$j + 1]) {
                        //$temp = $arr[$j];//存當前元素
                        //$arr[$j] = $arr[$j + 1];//把當前元素的值換成下一個元素的值
                        //$arr[$j + 1] = $temp;//把下一個元素的值換成上一個元素的值。
                        list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];//來自lovecn的評論,有時候思維有些固化。
                        $flag = 1;//交換位置就記錄。
                    }
                }
                if ($flag == 0) {//沒有發生交換位置,說明排序已經完成。可以推出迴圈。
                    break;
                }
            }
            return $arr;
        }

快速排序原理(遞回)

原理描述:

從陣列中取第一個值作為參照物,比這個值小的放在左邊,比這個值大的放在右邊,這樣就會有倆個新的陣列,遞回處理倆個陣列,然後左邊,參照物,右邊合併。注意:有遞回就要找到遞回出口,不然就會一直遞迴下去。

流程:

用文字敘述流程太麻煩,就從網上找了一個圖片,過程很清晰。

d3b5dd2e9cba2e19064e7d54ab9d844.png

程式碼:

    <?php
        function quickSort($arr)
        {
            $len = count($arr);
            //遞回出口
            if($len <= 1) {
                return $arr;
            }
            $markValue = $arr[0];//參照物。
            $left = $right = [];//定義左邊和右邊。
            for($i = 1; $i < $len; $i++) {//從1開始迴圈,因為第一個元素當作參照物。
                if($arr[$i] > $markValue) {//大於參照物的放在右邊。
                    $right[] = $arr[$i];
                } else {//小於和等於參照物的元素都放進左邊,這樣會避免如果陣列有重複元素時,會漏掉元素。
                    $left[] = $arr[$i];
                }
            }
            return array_merge(quickSort($left), [$markValue], quickSort($right));
        }

插入排序

原理描述:

將要排序的陣列分成倆個部分,取陣列第一個元素放有序集合中,剩下的放到無序集合中。將需要排序的數,與前面已經排好序的資料從後往前進行比較,直到找到小於或者等於它的數,使其插入到相應的位置。

我的記憶方法:

假設有倆個箱子,第一個箱子是透明並且是空的,要用來裝有序元素,第二個箱子是不透明並且是滿的,裝無序元素。(其實裝什麼都行,你喜歡的讓你容易記住的最好)。

1.第一步:在不透明箱子裡隨便拿一個元素,直接扔到透明的箱子裡
2.第二步:再從不透明的箱子裡拿出一個元素,放進透明箱子裡前,做比較。如果大就放後面,如果小就放前面。
3.重複第二步,但是我們每次需要比較的次數增加了,因為透明箱子裡元素多了,直到找到合適的位置。

流程:

1.gif

<?php
    function insertSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一個元素或者沒有元素,排序無意義。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            for($j = $i + 1; $j > 0; $j--){//每次比較次數增加。因為有序集合元素在增加。
                if ($arr[$j] < $arr[$j - 1]) {
                    list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];//交換位置。
                }
            }
        }
        return $arr;
    }

選擇排序

原理描述:

每次一次從陣列中取出最小元素或者最大元素,放到指定位置。

第一步:給第一個元素一個聖火令,和後面到每個元素比較,(我是取最小元素)。遇到比它小到元素就把這個聖火令給它,知道把聖火令交給最小元素手裡。

第二步:交換位置,聖火令交給第二哥元素,重複第一步。

流程:

2.gif

<?php
    function selectSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一個元素或者沒有元素,排序沒有意義。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            $p = $i;//給第一個元素聖火令。
            for($j =  $i + 1; $j < $len; $j++) {
                if ($arr[$j] < $arr[$p]) {//有聖火令的元素和後面的元素比較,把聖火令交給較小的元素。
                    $p = $j;
                }
            }
            list($arr[$p], $arr[$i]) = [$arr[$i], $arr[p]];
        }
        return $arr;
    }

以上就是PHP 排序演算法原理及總結的詳細內容,更多請關注TW511.COM其它相關文章!