<?php
/**
* 各种排序
* @author zhaojaingwei
* @since 2011/11/21 16:14
*
*/
$list = array(3,5,1,2,10,8,15,19,20);
//快排
function fast(&$list, $low, $high){
if($high - $low > 5){
while($low < $high){
$key = excute($list, $low, $high);
fast($list, $low, $key - 1);
//fast($list, $key + 1, $high);//普通递归实现
$low = $key + 1;//尾递归实现
}
}else{
insert($list);
}
}
//快排执行一次排序
function excute(&$list, $low, $high){
swap($list, $low, ($low + $high)/2);
$temp = $list[$low];
while($low < $high){
while($low < $high && $list[$high] > $temp){
$high --;
}
$list[$low] = $list[$high];
while($low < $high && $list[$low] < $temp){
$low ++;
}
$list[$high] = $list[$low];
}
$list[$low] = $temp;
return $low;
}
//堆排序
function heap(&$list){
buildheap($list);
for($i = count($list) - 1; $i > 0; $i --){
swap($list, $i, 0);
heapfy($list, 0, $i - 1);
}
}
//创建堆
function buildheap(&$list){
for($i = (count($list) - 2)/2; $i >= 0; $i --){
heapfy($list, $i, count($list) - 1);
}
}
//维护堆
function heapfy(&$list, $low, $high){
$temp = $list[$low];
for($i = ($low * 2 + 1); $i <= $high; $i = ($i * 2 + 1)){
if($i < $high && $list[$i] < $list[$i + 1]){
$i ++;
}
if($temp < $list[$i]){
swap($list, $i, $low);
$low = $i;
}else{
break;
}
}
$list[$low] = $temp;
}
//希尔排序
function shell(&$list){
$a = 0;
$code = count($list)/3 + 1;
while($code >= 1){
for($i = $code; $i < count($list); $i ++){
$a ++;
if($list[$i] < $list[$i - $code]){
$temp = $list[$i];
$list[$i] = $list[$i - $code];
$j = $i - 2*$code;
for(; $j >= 0 && $list[$j] > $temp; $j -= $code){
$list[$j + $code] = $list[$j];
$a ++;
}
$list[$j + $code] = $temp;
}
}
$code = $code/3;
}
echo $a;
}
//直接插入排序
function insert(&$list){
$a = 0;
for($i = 1; $i < count($list); $i ++){
$a ++;
if($list[$i] < $list[$i - 1]){
$temp = $list[$i];
$list[$i] = $list[$i - 1];
$j = $i - 2;
for(; $list[$j] > $temp; $j --){
$a ++;
$list[$j + 1] = $list[$j];
}
$list[$j + 1] = $temp;
}
}
echo $a;
}
//简单选择排序
function select(&$list){
$a = 0;
for($i = 0; $i < count($list); $i ++){
$min = $i;
$a ++;
for($j = $i + 1; $j < count($list); $j ++){
$a ++;
if($list[$j] < $list[$min]){
$min = $j;
}
}
if($min != $i)
swap($list, $i, $min);
}
echo $a;
}
//冒泡排序
function bubble(&$list){
$swap = true;
$a = 0;
for($i = 0; $i < count($list) && $swap; $i ++){
$swap = false;
$a ++;
for($j = count($list) - 2; $j >= $i; $j --){
$a ++;
if($list[$j] > $list[$j + 1]){
$swap = true;
swap($list, $j, $j + 1);
}
}
}
echo $a;
}
//移动或交换函数
function swap(&$list, $i, $j){
$temp = $list[$i];
$list[$i] = $list[$j];
$list[$j] = $temp;
}
?> 本文链接http://www.cxybl.com/html/wlbc/Php/20120607/28506.html