gpt4 book ai didi

PHP排序算法之简单选择排序(Simple Selection Sort)实例分析

转载 作者:qq735679552 更新时间:2022-09-29 22:32:09 31 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章PHP排序算法之简单选择排序(Simple Selection Sort)实例分析由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

本文实例讲述了PHP排序算法之简单选择排序(Simple Selection Sort)。分享给大家供大家参考,具体如下:

基本思想:

通过 n - i 次关键字间的比较,从 n - i + 1 个记录中选出关键字最小的记录,并和第 i (1 <= i <= n) 个记录交换,执行n-1趟 后就完成了记录序列的排序.

算法实现:

<?php//简单选择排序//交换函数function swap(array &$arr,$a,$b){  $temp = $arr[$a];  $arr[$a] = $arr[$b];  $arr[$b] = $temp;}//简单选择排序算法function SelectSort(array &$arr){  $count = count($arr);  for($i = 0;$i < $count - 1;$i ++){    //记录第$i个元素后的所有元素最小值下标    $min = $i;    for($j = $i + 1;$j < $count;$j ++){      if($arr[$j] < $arr[$min]){        $min = $j;      }    }    if($min != $i){      swap($arr,$min,$i);    }  }}$arr = array(9,1,5,8,3,7,4,6,2);SelectSort($arr);var_dump($arr);

运行结果:

array(9) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) [5]=> int(6) [6]=> int(7) [7]=> int(8) [8]=> int(9)}

复杂度分析:

在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录.

最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n).

简单选择排序是不稳定排序.

本文参考自《大话数据结构》,在此仅作记录,方便以后查阅,大神勿喷! 。

希望本文所述对大家PHP程序设计有所帮助.

最后此篇关于PHP排序算法之简单选择排序(Simple Selection Sort)实例分析的文章就讲到这里了,如果你想了解更多关于PHP排序算法之简单选择排序(Simple Selection Sort)实例分析的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

31 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com