- 冒泡排序法
在要排序的一组数中,对当前还未排好的序列,从前往后对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒,故名冒泡。
function bubbleSort1 ($a) {
$c = count($a);
for ($i=1; $i < $c; $i++) {
//该层循环控制 需要冒泡的轮数,即,数组长度-1
for ($j=0; $j < $c-$i; $j++) {
//该层循环控制 每轮冒泡的次数,即,数组长度-轮次
if ($a[$j] > $a[$j+1]) {
list($a[$j],$a[$j+1]) = [$a[$j+1],$a[$j]];
}
}
}
return $a;
}
- 选择排序法
在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
function selSort($arr){
$num=count($arr);
for($i = 0; $i< $num -1; $i++){
for($j=$i+1; $j<$num;$j++){
if($arr[$i] > $arr[$j]){
list($arr[$i],$arr[$j]) = [$arr[$j], $arr[$i]];
}
}
}
return $arr;
}
$arr = [2,6,2,8,2,34,5,9,2341,23];
print_r(selSort($arr));
- 插入排序
在要排序的一组数中,假设前面的数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。
function insertSort($a) {
$c = count($a);
for ($i=1; $i < $c; $i++) {
for ($j=$i-1; $j>=0 ; $j--) {
if ($a[$j]>$a[$j+1]) {
list($a[$j+1],$a[$j]) = [$a[$j],$a[$j+1]];
} else {
break;
}
}
}
return $a;
}
4、二分查找法
二分查找也称折半查找(Binary Search),时间复杂度O(logn),是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
function binarySearch($a, $n) {
$c = count($a);
if ($c < 1) {
return -1;
}
if ($c === 1) {
return $a[0] == $n ? 0 : -1;
}
$min = 0;
$max = $c -1;
$k = -1;
while ($min <= $max) {
$mid = intval(($min+$max)/2);
if ($a[$mid] > $n) {
$max = $mid - 1;
} else if ($a[$mid] < $n) {
$min = $mid + 1;
} else {
$k = $mid;
break;
}
}
return $k;
}
$astr = '12356789';
$a = str_split($astr);
var_dump(binarySearch($a, 8));
5、快速排序
顾名思义,这是实践中的一种快速的排序算法,它平均运行时间是O(N log N).该算法之所以特别快,主要是由于非常精炼和高度优化的内部循环。它的最坏情形性能为O(N^2)。像归并排序一样,快速排序也是一种分治的递归算法。其原理如下:
1、从数列中挑出一个元素,称为"基准"。(pivot)
2、重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
function quickSort($a) {
$c = count($a);
if (empty($a) || $c < 2) {
return $a;
}
$larr = [];
$rarr = [];
$mid = $a[0];
$midarr = [$mid];
for ($i=1; $i < $c; $i++) {
if ($a[$i] > $mid) {
$rarr[] = $a[$i];
} else if ($a[$i] < $mid) {
$larr[] = $a[$i];
} else {
$midarr[] = $a[$i];
}
}
$larr = quickSort($larr);
$rarr = quickSort($rarr);
return array_merge($larr, $midarr, $rarr);
}
$arr = [1, 0, 8, 3, 4, 1, -6, 1, -10];
print_r(quickSort($arr));
网友评论