比较排序算法（PHP）

浠ラ箍发布于2019-07-01 10:51 / 418人阅读

摘要：总结比较排序算法都是空间复杂度为的原地排序算法，其中冒泡排序和插入排序两两比较不会交换相等的记录，所以这两种排序都是稳定排序，而选择排序只是记录最小值最后进行交换，所以会破坏相对顺序，选择排序不是稳定算法。

冒泡排序

两两比较相邻记录的关键字，如果反序则交换，大的数字往下沉，一直到最大的出现在数组最后

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云服务器云服务器最快比较排序算法最快的基于比较的排序算法排序比较排序算法图解

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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