经典排序算法 - 选择排序
2023-09-14 08:57:25 时间
概述
含义:直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完。
特点:以从小到大排序为例:N个元素,每一趟比较找出最小的那个元素,放在头部;经过N-1趟比较,排序就出来了。
相当于每次从无序列表里找出一个最小数,放到左边;然后剩下的元素继续找出最小的,放在左边;直到排序完成。
题目:给出无需数组 [4,3,1,2],要求按照从小到大排序。
输出样例:
1
2
3
4
排序过程:
原数组:
4,3,1,2
- 第1趟:
3,4,1,2
1,4,3,2
1,4,3,2
- 第2趟:
首元素已排好序,固定住。
1,3,4,2
1,2,4,3
- 第3趟:
第2个元素已排好序,固定住。
1,2,3,4
实现:
/**
* 选择排序
* 时间O(N^2),最好O(N^2);空间O(1)
*
* 1、每趟都从待排序数字里找出最小的数字,循环找的过程中不交换;这趟查找结束的时候如果发现有更小的则进行交换一次。
* 2、第一趟开始的时候所有数字都是待排序。
* 3、每趟里的每次都先将待排序的第一个数当做最小的。
* @param $arr
*/
function SelectionSort($arr)
{
$len = count($arr);
//从第一个数开始,只需要N-1趟
for ($i = 0; $i < $len - 1; $i ++) {
$min = $i; //假设第一个数是最小的
//从第2个数开始与第一个数比较
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$j] < $arr[$min]) { //如果当前数小于min所在的数
$min = $j; //发现了当前数是更小的数, min更新为当前数
}
}
//比较min是否发生了变化,如果是则说明发现了更小的数,交换两数
if ($min != $i) {
$tmp = $arr[$i];
$arr[$i] = $arr[$min];
$arr[$min] = $tmp;
}
}
return $arr;
}
参考:
经典排序算法 - 选择排序Selection sort - kkun - 博客园
http://www.cnblogs.com/kkun/archive/2011/11/23/2260281.html
相关文章
- 【经典算法】直接选择排序
- 经典排序算法 - 插入排序&希尔排序
- 经典算法题每日演练——第二十五题 块状链表
- 算法系列15天速成——第五天 五大经典查找【中】
- PHP 中四大经典排序算法
- C#实现所有经典排序算法
- Jerry 2017年的五一小长假:8种经典排序算法的ABAP实现
- Atitit order algo 排序算法 算法之道 目录 1.1. 生活中常用的排序是插入排序和选择排序2 2. 0.1 算法分类2 3. .2 算法复杂度3 4. 十大经典排序算法(动图
- ML之RF:随机森林RF算法简介、应用、经典案例之详细攻略
- ML之LoR:逻辑回归LoR算法的简介、应用、经典案例之详细攻略
- Java中的六种经典比较排序算法:代码实现全解析
- 10 大经典排序算法 Python 版实现(附动图演示)
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-选择排序
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-归并排序
- 十大经典数据挖掘算法
- 白话经典算法系列之中的一个 冒泡排序的三种实现
- 白话经典算法系列之七 堆与堆排序
- 白话经典算法系列之六 高速排序 高速搞定
- 白话经典算法系列之五 归并排序的实现
- Python学习笔记十二之十大经典排序算法
- [MATLAB]手把手带你用MATLAB跑经典算法YOLOv5&训练自己的数据集(包含源码)
- 机器学习知识经验分享之三:基于卷积神经网络的经典目标检测算法
- DSA 经典数据结构与算法 学习心得和知识总结(一) |排序 十大排序算法汇总(C++)