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 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LeetCode 7. Reverse Integer分析代码

782
来自专栏zingpLiu

常用七种排序的python实现

算法复杂度分为时间复杂度和空间复杂度。其中, 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

855
来自专栏肖洒的博客

前端入门学习--JavaScript

大概了解了HTML和CSS,到了前端的精华JavaScript。 学习笔记,ALL FROM 廖雪峰的官方网站

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

C++ struct与union

编码运行环境:VS2012+Win32+Debug Win32既表示运行平台是Windows 32bits操作系统,又表示生成32bits的应用程序。

741
来自专栏noteless

[三] java虚拟机 JVM字节码 指令集 bytecode 操作码 指令分类用法 助记符

计算机指令就是指挥机器工作的指示和命令,程序就是一系列按一定顺序排列的指令,执行程序的过程就是计算机的工作过程。

2842
来自专栏SeanCheney的专栏

Python基础回顾基本数据类型和运算容器分支和循环函数、生成器和类map, reduce和filter列表生成(list comprehension)字符串文件操作和pickle异常多进程(mult

Python shell输入import this 可以看到The Zen of Python 基本数据类型和运算 基本数据类型 Python中最基本的数据类...

4557
来自专栏青玉伏案

窥探Swift之使用Web浏览器编译Swift代码以及Swift中的泛型

   有的小伙伴会问:博主,没有Mac怎么学Swift语言呢,我想学Swift,但前提得买个Mac。非也,非也。如果你想了解或者初步学习Swift语言的话,你可...

1865
来自专栏绿巨人专栏

[Java] 设计模式: Code Shape - 管理你的代码结构

4036
来自专栏Python中文社区

Python生成器的使用技巧详解

之前我们介绍了列表解析式,他的优点很多,比如运行速度快、编写简单,但是有一点我们不要忘了,他是一次性生成整个列表。如果整个列表非常大,这对内存也同样会造成很大压...

1233
来自专栏张善友的专栏

C# 4.0 Optional Parameters 和Named Parameters

Optional Parameters 是C# 4.0的特色之一,可减少重载函数的数量,却可达到相同的效果,加快开发效率。在使用上就跟C++一样,只需用等号为函...

2047

扫码关注云+社区