php 排列计算,php的几种排序算话

叁歲伎倆 2023-01-16 03:24 56阅读 0赞

冒泡算法

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

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

循环不变式特性：

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

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

分治算法：

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

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

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

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

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

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

$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++)

= $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;

原文：http://www.cnblogs.com/phplhs/p/3775551.html

php 排列计算,php的几种排序算话

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关使用 PHP 计算排列组合的方法

相关 php 排列计算,php的几种排序算话

相关 php的1和0排列组合_PHP的排列组合详解

相关 PHP生成随机数的几种方法

相关 PHP header 的几种用法

相关 php几种常用算法

相关 php安装扩展的几种方法

相关 PHP的几种运行模式cli、CGI、FastCgi、mod_php

相关 PHP 排列组合

相关 PHP精确计算 PHP高精度计算 PHP精度计算