冒泡算法

冒泡算话是简单的算话，基于循环不变式，也就是在下一次排序之前，前边的数是已经排序好，而且每次都是用当前数与前边的数一一比较。

循环不变式主要用来证明算法的正确性，即是证明执行步骤的的正确性，

循环不变式特性：

初始化：在循环的第一轮迭代开始之前，应该是正确

保持：如果在循环的某一次迭代开始时正确的，那么在下一次迭代之前他应该是正确的

分治算法：

是把 一个问题分成很多个规模较小和结构与问题类似的子问题，分别处理子问题在把子问题的结果合并成原问题的解。

分治模式在每一层递归上都有是三个模式

分解：把原问题分解成多个子问题

解决：递归解决子问题，如果子问题足够小直接求解

合并：在子问题的解答合并成原问题的解答；

冒泡排序是原地插入排序：

$arrs = array(8,3,2,5,-4,6,7,1,9,0,-9);
/**
*插入排序
O(N的平方)
*/
for($j = 0;$j < count($arrs); $j++)
{
$v = $arrs[$j];
for($i = $j; $i >= 0 && $arrs[$i-1] > $v;$i--)
{
$arrs[$i] = $arrs[$i-1];
$arrs[$i-1] = $v;
print_r($arrs);
}
}

$arrs = array(8,3,2,5,-4,6,7,1,9,0,-9);
/**
*插入排序
*/
$arr_len = count($arrs);
for($i = 0; $i < $arr_len;$i++)
{

for($ii = ($arr_len-2);$ii >= $i;$ii--)
{
$v = $arrs[$ii];
if($arrs[$ii] > $arrs[$ii + 1])
{
$arrs[$ii] = $arrs[$ii + 1];
$arrs[$ii+1] = $v;
}
}

}

/**
快速排序 分治方法
即是把数组分割为小数组，直到 数组等于二，或是1
此方法 计算最大时时间 2T(n/2)+N
*/

function maxsubsum($left=0,$right=0)
{
static $arr = array(8,3,2,5,-4,6,7,1,9,0,-9); //11
if($left==$right) return;
$center = intval(($left + $right)/2);
$maxleftsum = maxsubsum($left,$center);
$maxrightsum = maxsubsum($center+1,$right);
for($j=$left;$j<=$right;$j++)
{
$v = $arr[$j];
for($i = $j; $i >= 0 && $arr[$i-1] > $v;$i--)
{
$arr[$i] = $arr[$i-1];
$arr[$i-1] = $v;
}
print_r($arr);
}

}

//maxsubsum(0,10);

/**
*排序原理，基本原离基于插入排序交换了数组的值，让当值与它的前边的值一一比较，如果前边的值比其，则一一交换位置，当前值往前以以为，所以虽然每次都是两两比较，都是
如 8，3，5，9，2
其原理 获得当前元素的值，与其前面的元素值一一比较如果，如果前面的值大于这个元素则交换他们两个的位置，以为比较当前值时前边的远已经排序
如第一次
83592
第二次 $this = 5 = $arr(1); 此时比较 8和3,8>3因此交换
38592
比较第三次 $this = 5 = $arr(2);
先比较 8和5,8>5
因此交换 35892，也就是此时5已经往前已过一位。在比较 3和5其实就是在比较 $arr[0],$arr[1]
第四次比较 $this = 9 = $arr(3); 此时比较 8和9,8>9因此不交换 35892
第五次 $this = 2 = $arr(4); 此时比较 9和2 相当于比较35829

*
*/

快速排序是基于插入排序，对插入排序的一种优化，插入排序的一个很重要的有点就是接生空间，因其是原地排序不占用多余的内存。

快速排序是以后总分治的递归的插入排序。

快速排序的步骤：

分组（分解）：选取一个枢纽 R 是使得数组 A(i,j-1) 的小于 R A(j+1,n) 大于 R A[j] = R 因R已经排序所以不并入排序的数组中；

解决：递归的解决 A(i,j-1),A(j+1,n) 直到剩余两个数组元素就可以确定这两个数组元素的顺序一次的解决所有的元素的顺序

合并：因为子数组是原地排序，我们操作的只是数组的下标和值，因此当子数组排序完成的时候，排序也就排序好了

$arr = array(0=>2,1=>8,2=>7,3=>1,4=>3,5=>5,6=>6,7=>4,8=>10,9=>9,10=>13);

function kuaisu(&$arr,$left,$right)

{

　　if($left < $right){

　$q = paixu($arr,$left,$right); // 因为返回的 是的$j +1;

kuaisu($arr,$left,$q-2);

kuaisu($arr,$q,$right);　

}

}

function paixu(&$arr,$left,$right)

{

　　$key = $arr[$left]; //用于枢纽

　　$i = $left +1; //左边

for($j = $right; $j >= $i;$j--)  //先从右边跑

{

　　if($arr[$j] < $key)

{

　　while($i<=$j) // 从左边跑

{

　　if($arr[$i] > $key)

{

　　$arr[$i] = $tmp;

　　$arr[$i] = $arr[$j]; $arr[$j] = $arr[$i];

break;

}

　　$i++

}

}

}

$arr[$left] = $arr[$i-1]; $arr[$i-1] = $key;

return $i;

}