冒泡排序
【基本原理】
相邻两数依次比较，将小数放在前面，大数放在后面。第一趟结束，将最大的数放到了最后。第二趟结束，将最大的数放到了倒数第二。依次一直下去，直至最终完成排序。
冒泡排序，只需要使用两重循环实现，时间复杂度为O(n*n)。
立即学习“PHP免费学习笔记（深入）”；
【代码实现】
实现：两两比较，把小的数放在前面
<?php
function bubble_sort($array)
{
if(!is_array($array))
{
return false;
}
$len=count($array);
for($i=0;$i < $len-1;$i++)
{
$flag = false;
for($j=0;$j < $len-$i-1;$j++)
{
if($array[$j] > $array[$j+1])
{
$temp=$array[$j];
$array[$j]=$array[$j+1];
$array[$j+1]=$temp;
$flag = true;
}
}
if(! $flag)//本趟排序没有值交换，则提前终止程序
return $array;
}
}
//调用实现
$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);
print_r(bubble_sort($array));
?>希尔排序
【基本原理】
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1
本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。
的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 上述的分组和排序，直至所取的增量dt=1(dt 直接插入排序为止。 【代码实现】 实现：与增量间隔的数比较，直到把大的数放到最后 选择排序 【基本原理】 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 【代码实现】 实现：两次循环，全部比较找出最小元素的key(数组中的索引)，判断当前数与最小值key，不相等即交换值 文章来源：http://meego123.net/?post=126<?php
/**
* 数据结构中希尔排序PHP实现
*
* 时间复杂度为 O(N*(logN)2)
*/
function shell_sort($array)
{
if(!is_array($array))
{
return false;
}
$len=count($array);
$d=$len;//随机增量，初始值为数组长度，以不断除2取值
while($d >1)
{
$d=intval($d / 2);//分组间隔，2为n值，n值减少时，移动的趟数和数据增多
$temp=NULL;
$j=0;
for($i=$d;$i < $len;$i+=$d)
{
if($array[$i] < $array[$i-$d])
{
$temp=$array[$i];
$j=$i-$d;
while(($j >=0) && $temp < $array[$j])
{
$array[$j+$d]=$array[$j];
$j = $j - $d;
}
$array[$j+$d]=$temp;
}
}
}
return $array;
}
$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);
print_r(shell_sort($array));
?><?php
/**
* 数据结构中选择排序PHP实现
*
* 时间复杂度为 O(n2)
*/
function select_sort($array)
{
if(!is_array($array))
{
return false;
}
$len=count($array);
for($i=0;$i < $len;$i++)
{
$k=$i;
for($j=$i+1;$j < $len;$j++)
{
if($array[$k] > $array[$j])
{
$k=$j;
}
}
if($i!=$k){
$temp = $array[$i];
$array[$i] = $array[$k];
$array[$k] = $temp;
}
}
return $array;
}
$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);
print_r(select_sort($array));
?>
