常见算法排序

几种常用的算法php实现。

冒泡排序

冒泡排序(bubble sort)是一种交换排序,基本思想是:两两比较相邻纪录的关键字,如果反序则交换,直到没有反序的记录为止。(注意:是相邻) 时间复杂度为O(n^2)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php

function swap(&$a, &$b)
{
$t = $a;
$a = $b;
$b = $t;
}

function bubble($array)
{
$length = count($array);
$t = '';
$flag = true;

for ( $i = 0; $i < $length && $flag; ++$i) {
$flag = false;
for ( $j = $length-1; $j >= $i; $j-- ) {
if (!isset($array[$j+1])) continue;
if ( $array[$j] > $array[$j+1]) {
swap($array[$j], $array[$j+1]);
$flag = true;
}
}
}
return $array;
}

简单选择排序

简单选择排序法(simple selection sort)就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换之。 时间复杂度为O(n^2)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php

function swap(&$a, &$b)
{
$t = $a;
$a = $b;
$b = $t;
}

function selectSort($array)
{
$length = count($array);
$min = '';

for ( $i= 0; $i<$length; ++$i) {
$min = $i;

for ( $j = $i+1; $j < $length; ++$j) {
if ( $array[$min] > $array[$j]) {
$min = $j;
}
}
if ( $i != $min ) {
swap($array[$i], $array[$min]);
}
}
return $array;
}

插入排序

直接插入排序(straight insertion sort),基本操作是将一个记录插入到已经排好序的有序表中,复杂度为O(n^2),因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。描述如下

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php

function insertSort($array)
{
$length = count($array);
$tmp = '';

for ($i=1; $i<$length; ++$i) {
if ($array[$i] < $array[$i-1]) {
$tmp = $array[$i];
for ($j = $i-1; $j > -1 && $array[$j] > $tmp; --$j) {
$array[$j+1] = $array[$j];
}
$array[$j+1] = $tmp;
}
}
return $array;
}

希尔排序

希尔排序(shell sort),不稳定排序。

代码如下,增量为n/2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php

function shellSort($array)
{
$length = count($array);

for ($gap = $length >> 1; $gap > 0; $gap >>= 1) {
for ( $i = $gap; $i < count($array); ++$i ) {
$tmp = $array[$i];
for ( $j = $i - $gap; $j >= 0 && $array[$j] > $tmp; $j -= $gap ) {
$array[$j+$gap] = $array[$j];
}
$array[$j+$gap] = $tmp;
}
}

return $array;
}