常用排序算法的核心代码
在《常用排序算法》这篇文章中我们大概介绍了各种排序算法的思想和实现步骤。本篇我将这几种排序算法的核心代码奉献给大家。
所有排序算法的完整代码在github上，点此进行下载 。
1. 直接插入排序
下面是封装的直接插入排序的函数
function InsertSort(&$arr){
for($i=1;$i<count($arr);$i++){
$p = $arr[$i];
for($j=$i-1;$j>=0;$j--){
if($arr[$j]>$p){
$arr[$j+1] = $arr[$j];
}else{
break;
}
}
$arr[$j+1] = $p;
}
}
2. 折半插入排序
下面是封装的折半插入排序的函数
function HalfInsertSort(&$arr){
for($i=1;$i<count($arr);$i++){
if($arr[$i]<$arr[$i-1]){
//使用二分查找法查找适当的位置
$low = 0;
$high = $i-1;
$pos = floor(($low+$high)/2);
$key = $arr[$i];
while($low<$high){
if($arr[$pos]>$key){
$high = $pos-1;
}elseif($arr[$pos]<=$key){
$low = $pos+1;
}
$pos = ceil(($low+$high)/2);
}
//二分查找法结束
if($arr[$pos]>$arr[$i]){
$pos = $pos-1;
}
for($j=$i-1;$j>$pos;$j--){
$arr[$j+1]=$arr[$j];
}
$arr[$j+1] = $key;
}
}
}
3. 表插入排序
下面是封装的表插入排序的函数
function TableInsertSort(&$arr,&$link){
$link[0]=array('next'=>1);//初始化链表 $link第一个元素仅仅作为头部
$link[1]=array('next'=>0); //将第一个元素放入$link
/*
* 开始遍历数组 从第二个元素开始
*/
for($i=2;$i<=count($arr);$i++){
$p = $arr[$i]; //存储当前待排序的元素
$index =0;
$next = 1; //从开始位置查找链表
while($next!=0){
if($arr[$next]['age']<$p['age']){
$index = $next;
$next = $link[$next]['next'];
}
else break;
}
if($next == 0){
$link[$i]['next'] = 0;
$link[$index]['next'] = $i;
}else{
$link[$i]['next']=$next;
$link[$index]['next']=$i;
}
}
}
4.希尔排序
下面是封装的希尔排序的函数
function ShellSort(&$arr){
/*
* 首先初始化 增量 数组长度/2 取整 floor() 函数向下取整 对于增量每次循环都由 当前增量/2
*/
for($dl=floor(count($arr)/2);$dl>=1;$dl=floor($dl/2)){
/*
* 每次从 增量的位置开始，直到数组递增变量达到数组的长度
*/
for($j=$dl;$j<count($arr);$j++){
for($i=$j-$dl;$i>=0;$i-=$dl){
if($arr[$i+$dl]<$arr[$i]){
$temp = $arr[$i+$dl];
$arr[$i+$dl]=$arr[$i];
$arr[$i]=$temp;
}
}
}
}
}
5.归并排序
下面是归并排序的递归实现
function MergeSortRecurse(&$arr,$l,$r){
if($r <= $l) return ;
$m = floor(($l+$r)/2);
MergeSort($arr,$l,$m);
MergeSort($arr,$m+1,$r);
$arr = Merge($arr,$l,$m,$r);
}
下面是归并排序的非递归方式的实现
function MergeSort(&$arr){
$stack = array();
$stack1 = array();
$temp = array(0,count($arr)-1,floor((0+count($arr)-1)/2));
array_push($stack,$temp);
while(count($stack)>0){
$temp = array_pop($stack);
array_push($stack1,$temp);
if($temp[0]<$temp[2]){
array_push($stack,array($temp[0],$temp[2],floor(($temp[0]+$temp[2])/2)));
}
if($temp[2]+1<$temp[1]){
array_push($stack,array($temp[2]+1,$temp[1],floor(($temp[2]+1+$temp[1])/2)));
}
}
while(count($stack1)>0){
$temp = array_pop($stack1);
$arr = Merge($arr,$temp[0], $temp[2], $temp[1]);
}
}
6. 快速排序
下面是快速排序的递归方式的实现
function FastSortRecurse(&$arr,$s,$e){
if($s>=$e) return ;
$nextP = FindPiv($arr,$s,$e); //找到下一个基准所在位置
FastSortRecurse($arr,$s,$nextP-1);
FastSortRecurse($arr,$nextP+1,$e);
}
下面是快速排序的非递归方式的实现
function FastSort(&$arr){
$stack = array();
array_push($stack,array(0,count($arr)-1));
while(count($stack)>0){
$temp = array_pop($stack);
$p = FindPiv($arr, $temp[0], $temp[1]);
if($p+1<$temp[1]) array_push($stack,array($p+1,$temp[1]));
if($temp[0]<$p-1) array_push($stack,array($temp[0],$p-1));
}
}
7. 堆排序
下面是封装的堆排序的函数——其实现是大顶堆
function HeapSort(&$arr){
$start = floor(count($arr)/2); //找到最后一个非叶子节点
$end = count($arr);
/*
* 构造大顶堆
*/
while($start>0){
$p = $start;
while($p){
$p = MakeHeapChild($arr,$p,$end);
}
$start-- ;
}
//构造大顶堆结束
/*
* 交换顶部节点和最后一个叶子节点 依次调整大顶堆
*/
while($end>1){
swap($arr,0,$end-1);
$end--;
$p = 1;
while($p){
$p = MakeHeapChild($arr,$p,$end);
}
}
}
8.选择排序
下面是封装的选择排序的函数
function SelectSort(&$arr){
$end = count($arr)-1;
do{
$p = 0;
for($i=0;$i<=$end;$i++){
if($arr[$i]>$arr[$p]){
$p = $i;
}
}
swap($arr,$p,$end);
}while(--$end>0);
}
9. 冒泡排序
下面是封装的冒泡排序的实现函数
function BubbleSort(&$arr){
$end = count($arr)-1;
while($end>0){
$flag = false;
for($i=0;$i<$end;$i++){
if($arr[$i]>$arr[$i+1]){
swap($arr,$i,$i+1);
$flag = true;
}
}
if(!$flag) break;
$end--;
}
}
10. 基数排序——LSD
下面是封装的基数排序的LSD方式的函数
function LSD_RadixSort(&$arr){
//得到序列中最大位数
$d = FindMaxBit($arr);
$bucket = array();
//初始化队列
for($i=0;$i<10;$i++){
$bucket[$i]=array('num'=>0,'val'=>array());
}
/*
* 开始进行分配
*/
$radix = 1;
for($i=1;$i<=$d;$i++){
for($j=0;$j<count($arr);$j++){
$k = floor($arr[$j]/$radix)%10;
$bucket[$k]['num']++;
array_push($bucket[$k]['val'],$arr[$j]);
}
$arr = array();
foreach ($bucket as $key => $val) {
for ($j = 0; $j < $val['num']; $j ++) {
$arr[] = $val['val'][$j];
}
}
for($l=0;$l<10;$l++){
$bucket[$l]=array('num'=>0,'val'=>array());
}
$radix *= 10;
}
}
11. 基数排序——MSD
下面是封装的基数排序的MSD方式的函数
function MSD_RadixSort(&$arr,$r){
$radix = pow(10,$r-1);
$bucket = array();
//初始化队列
for($i=0;$i<10;$i++){
$bucket[$i]=array('num'=>0,'val'=>array());
}
for($j=0;$j<count($arr);$j++){
$k = floor($arr[$j]%pow(10,$r)/$radix);
$bucket[$k]['num']++;
array_push($bucket[$k]['val'],$arr[$j]);
}
for($j=0;$j<10;$j++){
if($bucket[$j]['num']>1){
MSD_RadixSort($bucket[$j]['val'],$r-1);
}
}
/*
* 将桶中的数据收集起来，此时序列是有序的
*/
$arr = array();
for($j=0;$j<10;$j++){
for($i=0;$i<count($bucket[$j]['val']);$i++){
$arr[] = $bucket[$j]['val'][$i];
}
}
}
希望本文对大家有帮助。
本文转载自：迹忆客（https://www.jiyik.com）
以上是 常用排序算法的核心代码 的全部内容， 来源链接： utcz.com/z/290053.html
