比較排序算法（PHP）

浠ラ箍發布于2019-07-01 10:51 / 433人閱讀

摘要：總結比較排序算法都是空間復雜度為的原地排序算法，其中冒泡排序和插入排序兩兩比較不會交換相等的記錄，所以這兩種排序都是穩定排序，而選擇排序只是記錄最小值最后進行交換，所以會破壞相對順序，選擇排序不是穩定算法。

冒泡排序

兩兩比較相鄰記錄的關鍵字，如果反序則交換，大的數字往下沉，一直到最大的出現在數組最后

function swap(&$x, &$y) {
    $temp = $x;
    $x = $y;
    $y = $temp;
}

function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
    for ($i = 0; $i < count($arr) - 1; $i++) {    //控制循環的次數
        for ($j = 0; $j < count($arr) - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                swap($arr[$j], $arr[$j + 1]);
            }
        }
    }
}

改進的冒泡排序

第一層循環不變，第二層循環冒泡變成從后往前，這樣做可以在冒泡的過程中盡可能的將小的數據向前冒。

function bubble_sort(&$arr)
{
    for ($i=0;$i$i;$j--) {
            if ($arr[$j-1]>$arr[j]) {
                swap($arr[j-1],$arr[j]);
            }
        }
    }
}

插入排序

將一個記錄插入到已經排好序的有序表中

function insertion_sort(&$arr) 
{//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
    for ($i = 1; $i < count($arr); $i++) {
         $temp = $arr[$i];
         for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
             $arr[$j + 1] = $arr[$j];
         }
         $arr[$j + 1] = $temp;
    }
}

選擇排序

通過n-i次關鍵字的比較，找出n-i+1個記錄中最小的記錄，并和第i個記錄交換

function select_sort(&$arr)
{
    for ($i = 0;$i < count($arr);$i++) {
        $min = $i;
        for ($j = count($arr)-1;$j > $i;$j--) {
            if ($arr[$j] < $arr[$min]) {
                $min = $j;
            }
        }
        if ($min != $i) {
            swap($arr[$i],$arr[$min]);
        }
    }
}

為什么插入排序比冒泡排序好

兩個算法的時間復雜度都是O（n^2），但是冒泡排序每次交換記錄時都要進行三次賦值操作，而插入排序因為有哨兵變量，所以只有一步賦值操作，減少了排序時間。

總結

比較排序算法都是空間復雜度為O（1）的原地排序算法，其中冒泡排序和插入排序兩兩比較不會交換相等的記錄，所以這兩種排序都是穩定排序，而選擇排序只是記錄最小值最后進行交換，所以會破壞相對順序，選擇排序不是穩定算法。

云服務器 GPU云服務器最快比較排序算法最快的基于比較的排序算法排序比較排序算法圖解

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

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

PHP面試：盡可能多的說出你知道的排序算法

摘要：良好的排序算法具有進行最少的比較和交換的特征。冒泡排序是一個基于比較的排序算法，被認為是效率最低的排序算法之一。現在讓我們使用實現冒泡排序算法。插入排序到目前為止，我們已經看到了兩種基于比較的排序算法。預警本文適合對于排序算法不太了解的新手同學觀看，大佬直接忽略即可。因為考慮到連貫性，所以篇幅較長。老鐵們看完需要大概一個小時，但是從入門到完全理解可能需要10個小時(哈哈哈，以我自己...

objc94 2019-07-01 10:39 評論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
PHP算法之四大基礎算法

摘要：而在證明算法是正確的基礎上，第二步就是分析算法的時間復雜度。算法的時間復雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出算法的優劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言雖然工作中，你覺得自己并沒有涉及到算法這方面的東西，但是算法是程序的...

isLishude 2019-07-01 12:31 評論0 收藏0
PHP數組排序算法實現(14種)

摘要：本文將介紹快速排序計數排序梳排序堆排序歸并排序希爾排序選擇排序插入排序地精排序聯合冒泡排序雞尾酒排序冒泡排序奇偶排序使用標志的冒泡排序種排序算法的實現。是一種不穩定的排序算法。本文將介紹快速排序、計數排序、梳排序、堆排序、歸并排序、希爾排序、選擇排序、插入排序、地精排序、聯合冒泡排序、雞尾酒排序、冒泡排序、奇偶排序、使用標志的冒泡排序14種排序算法的實現。本文是由于閱讀了文章《測試評...

aisuhua 2019-06-27 13:54 評論0 收藏0
PHP排序算法之冒泡排序

摘要：一冒泡排序原理對一組數據，比較相鄰數據的大小，將值小數據在前面，值大的數據放在后面。通過以上五輪排序，若干次比較，我們有理由推斷出一個結論對于一個長度為的數組，我們需要排序輪，每輪要比較次。一、冒泡排序　　原理：對一組數據，比較相鄰數據的大小，將值小數據在前面，值大的數據放在后面。（以下都是升序排列，即從小到大排列）　　舉例說明： $arr = array(6, 3, 8,...

Raaabbit 2019-07-01 10:30 評論0 收藏0