比较排序算法（PHP）
2024-08-24 10:15:01
冒泡排序
- 两两比较相邻记录的关键字，如果反序则交换，大的数字往下沉，一直到最大的出现在数组最后
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<count($arr);$i++) {
for ($j=count($arr)-1;$j>$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）的原地排序算法，其中冒泡排序和插入排序两两比较不会交换相等的记录，所以这两种排序都是稳定排序，而选择排序只是记录最小值最后进行交换，所以会破坏相对顺序，选择排序不是稳定算法。
原文地址：https://segmentfault.com/a/1190000016768646
最新文章
- Atitit.log日志技术的最佳实践attilax总结
- 使用Cordova编译Android平台程序提示：Could not reserve enough space for 2097152KB object heap
- [HDOJ5938]Four Operations（暴力，DFS）
- POJ 1719 二分图最大匹配（记录路径）
- 【TOP10 APP】这些应用成了AppCan千人大会的焦点
- 在C语言中嵌入汇编语言
- Ubuntu关闭图形界面
- （剑指Offer）面试题22：栈的压入、弹出序列
- Browser 对象
- c++学习笔记2（c++简单程序）
- OrderedDict
- 直播视频插件--sewise player
- javascript eval和JSON之间的关系
- bzoj 4830: [Hnoi2017]抛硬币 [范德蒙德卷积 扩展lucas]
- （三）SpringBoot基础篇- 持久层，jdbcTemplate和JpaRespository
- oracle跨库连接查询
- java调用百度地图API
- Ubuntu12.04下Qt连接MySQL数据库
- hbase的写和读，大合并和小合并
- Windows下使用MakeFile(Mingw)文件