专栏首页决胜机器学习PHP数据结构(二十三) ——快速排序

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),作者:linhxx

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP数据结构(二十五) ——并归排序

    PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

    用户1327360
  • PHP数据结构(二十六) ——基数排序实现36进制数排序

    PHP数据结构(二十六)——基数排序实现36进制数排序 (原创内容,转载请注明来源,谢谢) 一、概述 插入排序、选择排序、快速排序等,都是通过关键字之间的比...

    用户1327360
  • PHP数据结构(二十二) ——快速排序

    PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行...

    用户1327360
  • PHP数据结构(二十四) ——堆排序

    PHP数据结构(二十四)——堆排序 (原创内容,转载请注明来源,谢谢) 一、定义 堆排序也属于一种选择排序,效率较高且空间占用相对较少。 堆的定义:n个元...

    用户1327360
  • PHP源码目录结构

    根目录: / 这个目录包含的东西比较多,主要包含一些说明文件以及设计方案。 其实项目中的这些README文件是非常值得阅读的例如: /README.PHP4-...

    joshua317
  • 使用xtrabackup备份后,有时候 apply-log 后,2个文件的位移点不一致的解答

    使用xtrabackup备份后,有时候 apply-log 后,2个文件的位移点不一致的解答:

    二狗不要跑
  • mysql行转列转换

    皇上得了花柳病
  • 程序员笔记|Zookeeper 扩展之殇

    基于公司发展硬性需求,生产VM服务器要统一迁移到ZStack 虚拟化服务器。检查自己项目使用的服务器,其中zookeeper集群中招,所以需要进行迁移。

    宜信技术学院
  • iOS图像处理系列 - 双重曝光技术的GPUImage实现

    多重曝光是一种拍摄技法,不过为了烘托气氛,常常选择这种技法,多重曝光技术一般用来拍摄双影或多影照片。可以拍摄出魔术般无中生有的效果,这也正是它的独具魅力之处,所...

    天天P图攻城狮
  • scala-sparkML学习笔记:迁移文件/ 通过 .!! 隐式方法直接执行系统命令

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    MachineLP

作者介绍

精选专题

活动推荐

扫码关注云+社区

领取腾讯云代金券