PHP数据结构(二十三) ——快速排序

PHP数据结构(二十三)——选择排序

(原创内容,转载请注明来源,谢谢)

一、概述

选择排序的基本思想,是每一趟在n-i+1(i=1,2…n-1)个记录中选取关键字最小的记录作为第i个记录。选择排序分为简单选择排序、树形选择排序、堆排序。

二、简单选择排序

简单选择排序,即完全按照上述的说法进行排序。时间复杂度O(n2)。由于比较简单,不具体描述。

1、算法

1)遍历整个数组,找到最小值放置于第一个位置。

2)遍历从第二个位置至末尾的数组,找到最小值放在第二个位置。

3)重复上述操作直到排序完成。

2、实现源码如下

                  //简单选择排序
                  public function simpleSelectSort(array$arr = array()){
                   $arr= $this->_checkNeedSort($arr);
                   if(!$arr){
                            return$arr;
                   }
                   //长度只有1直接返回
                   if(1== count($arr)){
                            return$arr;
                   }
                   //遍历数组,第i次取第i小值放置于第i-1的位置
                   //由于n-1次已经可以遍历完,故不需要第n次遍历
                   for($i=0;$i<count($arr)-1;$i++){
                            //暂存临时最小值与关键字
                            $min= $arr[$i];
                            $minIndex= $i;
                            for($j=$i+1;$j<count($arr);$j++){
                                     //如果最小值比暂存小,则更新暂存
                                     if($arr[$j]<$min){
                                               $min= $arr[$j];
                                               $minIndex= $j;
                                     }
                            }
                            //将暂存的最小值替换到第i个位置
                            $tmp= $arr[$i];
                            $arr[$i]= $arr[$minIndex];
                            $arr[$minIndex]= $tmp;
                   }
                   return$arr;
         }

三、树形选择排序

树形选择排序是利用简单选择排序在每一次排序的结果进行的排序,又被称为锦标赛排序。两两进行排序,小的值再两两排序,直至选出最小值。再进行第二轮的排序选择次小值。树形选择排序时间复杂度是O(nlogn)。

1、算法

1)构造一棵满二叉树,其叶子节点都在同一层,且叶子节点包含了所有的待排序数组。

2)两两节点进行比较,关键字对应的值小的那一个进入父节点,叶子节点的位置值置成无穷大。

3)直至比出根节点。则为最小值。

4)再次遍历此树,直至构造完成全部的值。

实际实现中,由于树形选择排序必须用完全二叉树,而完全二叉树的父节点和其子节点的编号关系是确定的,可以用数组来表达。

数组表达的方式,假设根节点为0,从左往右、从上往下编号,则第一层为0,第二层为1、2(父节点都是0),第三层为3、4、5、6(父节点3、4的是1,5、6的是2)。

依次类推,两两一组,可以确定,父节点编号=(左节点编号-1)/2,或父节点编号=右节点编号/2-1。因此可以两两一组进行遍历。

2、树形选择排序如下图所示(图片来自网络):

3、实现源码如下

         //树形选择排序
         publicfunction treeSelectSort(array $arr = array()){
                   $arr= $this->_checkNeedSort($arr);
                   if(!$arr){
                            return$arr;
                   }
                   //长度只有1直接返回
                   if(1== count($arr)){
                            return$arr;
                   }
                   //确定数组长度,即完全二叉树叶子节点的个数
                   $arrLength= count($arr);
                   //完全二叉树
                   $arrTreeNodes= array();
                   //完全二叉树节点总数为叶子节点个数*2-1
                   $treeNodesLength= 2 * $arrLength -1;
                   //倒序将数组放置于完全二叉树数组的末尾,构造叶子节点
                   for($i=$arrLength-1,$j=0;$i>=0;$i--,$j++){
                            $arrTreeNodes[$treeNodesLength-1-$j]= $arr[$i];
                   }
                   //补全完全二叉树叶子节点以外的节点。i每两个进行比较,从最后一个节点起,相当于每次都在右节点,因此其父节点位置为i/2-1
                   for($i=$treeNodesLength-1;$i>0;$i=$i-2){
                            //取小的值为父节点的值
                            $arrTreeNodes[$i/2-1]= $arrTreeNodes[$i] < $arrTreeNodes[$i-1] ? $arrTreeNodes[$i] :$arrTreeNodes[$i-1];
                   }
                   //从0起生成最终的数组
                   $low= 0;
                   while($low< $arrLength){
                            //每次生成树后,其当前的第一个值(下标是0)即为最小值
                            $curMin= $arrTreeNodes[0];
                            //最小值放入最终的数组
                            $arr[$low++]= $curMin;
                            //从最后一个元素起,找结果为最小值的下标
                            $curMinIndex= $treeNodesLength - 1;
                            //相等时找到下标
                            while($curMin!= $arrTreeNodes[$curMinIndex]){
                                     $curMinIndex--;
                            }
                            //将结果最小的值设置成无穷大
                            $arrTreeNodes[$curMinIndex]= INF;
                            //找其父节点即父节点的父节点,直至根节点
                            while(0< $curMinIndex){
                                     //如果是偶数,说明是右节点,父节点是i/2-1,要比较的是i和i-1
                                     if(0== $curMinIndex%2){
                                             $arrTreeNodes[$curMinIndex/2-1]= $arrTreeNodes[$curMinIndex] < $arrTreeNodes[$curMinIndex-1] ?$arrTreeNodes[$curMinIndex] : $arrTreeNodes[$curMinIndex-1];
                                               $curMinIndex= $curMinIndex / 2 - 1;
                                     }else{
                                               //如果是奇数,说明是左节点,父节点是(i-1)/2,要比较的是i和i+1
                                               $arrTreeNodes[($curMinIndex-1)/2]= $arrTreeNodes[$curMinIndex] < $arrTreeNodes[$curMinIndex+1] ?$arrTreeNodes[$curMinIndex] : $arrTreeNodes[$curMinIndex+1];
                                               $curMinIndex= ($curMinIndex - 1) / 2;                                       
                                     }
                            }
                   }
                   return$arr;
         }

4、评价

树形选择排序由于需要额外的空间较多,而且有大量的INF(PHP中表示无穷大的值),浪费空间较多,实际中不常用,而往往使用优化版的树形选择排序——堆排序。

堆排序的内容见下文。

——written by linhxx 2017.07.20

相关阅读:

PHP数据结构(二十二) ——快速排序

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十) ——其他插入排序

PHP数据结构(十九) ——B+树

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信宝典

Linux学习 - SED操作,awk的姊妹篇

awk和sed想一对兄妹,一个出现,就会问起另一个。现在,都来了。 sed基本参数解释 sed是stream editor的简称,擅长对文件进行各种正则操作、插...

1736
来自专栏前端架构

排序算法图文讲解(php,javascript,java)

大湿们常说,程序=算法+数据结构!砖家门的资料也介绍的非常详细,但是,比如小白我来讲,看的还是昏昏欲睡的感觉。尼玛!就不能简单些吗?我想,各位攻城师和程序猿们也...

802
来自专栏landv

C语言_函数【转】

1443
来自专栏企鹅号快讯

Python笔记·第一章——Python基础(一)

Python的简介 1、Python的由来与版本 1.1 python的由来 python的创始人为吉多·范罗苏姆(Guido van Rossum)。1989...

1917
来自专栏企鹅号快讯

看完这篇文章我知道至少85%的人是没有入门Python的!花两周整理

以前刚学编程的时候就对Python略有耳闻,不过学校只有C,C++,Java,C#。和PHP有句"PHP是最好的语言" 这种家喻户晓的骚话一样,Python也有...

2137
来自专栏C/C++基础

Linux命令(41)——tr命令

tr用来转换或者删除一段文字。tr是translate(转换的缩写),功能的英文示意是:translate or delete characters。tr所有的...

851
来自专栏AI派

Numpy 修炼之道 (12)—— genfromtxt函数

genfromtxt的唯一强制参数是数据的源。它可以是字符串,字符串列表或生成器。如果提供了单个字符串,则假定它是本地或远程文件或具有read方法的打开的类文件...

6514
来自专栏架构师之路

perl语言十分钟入门【零基础可入】

零基础,perl语言,10分钟入门 1.Hello,World #!/usr/bin/perl -w print ("hello,world!\n"); #pr...

3457
来自专栏desperate633

深入理解SortSet类型的使用及应用Redis 有序集合(sorted set)SortSet的应用场景SortSet的常用命令

Redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。

842
来自专栏申龙斌的程序人生

Eclipse油藏模型解析程序

2010年的时候,三维可视化项目中要读取eclipse建模软件产生的三维模型网格数据,经过连续多天的奋战,终于搞明白eclipse数模软件输出的egrid、in...

2767

扫描关注云+社区