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
相关阅读：