写点什么

冒泡插入选择排序以及 PHP 实现

发布于: 2021 年 03 月 13 日
冒泡插入选择排序以及PHP实现

一、排序方法与复杂度归类

  1. 几种最经典、最常用的排序方法:冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。

  2. 复杂度归类

  • 冒泡排序、插入排序、选择排序 O(n^2)

  • 快速排序、归并排序 O(nlogn)

  • 计数排序、基数排序、桶排序 O(n)

二、如何分析一个“排序算法”?

算法的执行效率

  1. 最好、最坏、平均情况时间复杂度。

  2. 时间复杂度的系数、常数和低阶。

  3. 比较次数,交换(或移动)次数。

排序算法的稳定性

  1. 稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

  2. 稳定性重要性:可针对对象的多种属性进行有优先级的排序。

  3. 举例:给电商交易系统中的“订单”排序,按照金额大小对订单数据排序,对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序,排序完成后用稳定排序算法按照订单金额重新排序。

排序算法的内存损耗

原地排序算法:特指空间复杂度是 O(1)的排序算法。

三、冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。

稳定性

冒泡排序是稳定的排序算法。

空间复杂度

冒泡排序是原地排序算法。

时间复杂度

  1. 最好情况(满有序度):O(n)。

  2. 最坏情况(满逆序度):O(n^2)。

  3. 平均情况:

1. “有序度”和“逆序度”:对于一个不完全有序的数组,如 4,5,6,3,2,1,有序元素对为 3 个(4,5),(4,6),(5,6),有序度为 3,逆序度为 12;对于一个完全有序的数组,如 1,2,3,4,5,6,有序度就是n*(n-1)/2,也就是 15,称作满有序度;逆序度=满有序度-有序度;冒泡排序、插入排序交换(或移动)次数=逆序度。

2. 最好情况下初始有序度为n*(n-1)/2,最坏情况下初始有序度为 0,则平均初始有序度为n*(n-1)/4,即交换次数为n*(n-1)/4,因交换次数<比较次数<最坏情况时间复杂度,所以平均时间复杂度为 O(n^2)。

代码实现

public function bubbleSort($array){    $count = count($array);    if ($count <= 0) {        return false;    }    for ($i = 0; $i < $count; $i++) {        // 提前退出冒泡循环的标志位        $flag = false;        for ($j = $count - 1; $j > $i; $j--) {            if ($array[$j] < $array [$j - 1]) {                $tmp = $array[$j];                $array[$j] = $array[$j - 1];                $array [$j - 1] = $tmp;                $flag = true;            }        }        if (!$flag) {            break;        }    }    return $array;}
复制代码


四、插入排序

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素,即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置,直到未排序区间为空。

稳定性

插入排序是稳定的排序算法。

空间复杂度

插入排序是原地排序算法。

时间复杂度:

  1. 最好情况:O(n)。

  2. 最坏情况:O(n^2)。

  3. 平均情况:O(n^2)(往数组中插入一个数的平均时间复杂度是 O(n),一共重复 n 次)。

代码实现

public function insertionSort(array $a){    $n = count($a);    if ($n <= 1) {        return false;    }    for ($i = 1; $i < $n; $i++) {        $value = $a[$i];        for ($j = $i - 1; $j >= 0; --$j) {            if ($a[$j] > $value) {                $a[$j + 1] = $a[$j];            } else {                break;            }        }        $a[$j + 1] = $value;    }    return $a;}
复制代码


五、选择排序

选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾,直到未排序区间为空。

稳定性

选择排序不是稳定的排序算法。

空间复杂度

选择排序是原地排序算法。

时间复杂度:(都是 O(n^2))

  1. 最好情况:O(n^2)。

  2. 最坏情况:O(n^2)。

  3. 平均情况:O(n^2)。

代码实现

/*** 选择排序* 时间复杂度O(n^2)* @param array $list* @return array*/public function selectionSort(array $list){    $n = count($list);    for ($i = 0; $i < $n - 1; $i++) {        $min = $i;        for ($j = $i + 1; $j < $n; $j++) {            if ($list[$j] < $list[$min]) {                $min = $j;            }        }        if ($min != $i) {            $value = $list[$min];            $list[$min] = $list[$i];            $list[$i] = $value;        }    }    return $list;}
复制代码


思考

  1. 冒泡排序和插入排序的时间复杂度相同,都是O(n^2),在实际的软件开发中,为什么我们更倾向于使用插入排序而不是冒泡排序算法呢?

答:从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个,所以在对相同数组进行排序时,冒泡排序的运行时间理论上要长于插入排序。

  1. 这种排序算法,都是基于数组实现的。如果数据存储在链表中,这三种排序算法还能工作吗?如果能,那相应的时间、空间复杂度又是多少呢?

答:是否允许修改链表的节点 value 值,还是只能改变节点的位置。一般而言,考虑只能改变节点位置,冒泡排序相比于数组实现,比较次数一致,但交换时操作更复杂;插入排序,比较次数一致,不需要再有后移操作,找到位置后可以直接插入,但排序完毕后可能需要倒置链表;选择排序比较次数一致,交换操作同样比较麻烦。综上,时间复杂度和空间复杂度并无明显变化,若追求极致性能,冒泡排序的时间复杂度系数会变大,插入排序系数会减小,选择排序无明显变化


发布于: 2021 年 03 月 13 日阅读数: 9
用户头像

多读书多看报,少吃零食多睡觉 2018.08.07 加入

还未添加个人简介

评论

发布
暂无评论
冒泡插入选择排序以及PHP实现