常用排序算法的 PHP 实现
2017-09-21 本文已影响91人
Stone_Zhuo
排序概念
在计算机领域，排序是将原本无序的队列按照一定的规则分布而成为有序队列的过程，在程序开发中应用比较广泛。
排序种类
常见的排序算法有：冒泡排序，直接插入排序，折半插入排序，快速排序，计数排序，希尔排序，梳排序，选择排序。
排序实例
- 冒泡排序
冒泡排序是通过遍历队列并依次比较相邻的两个元素，把不符合顺序要求的元素进行交换，重复这一过程知道队列元素全部符合顺序要求为止。排序过程就好像水中的气泡往上冒一样，所以被成为冒泡排序。PHP实例如下：
// 由小到大排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
for ($j = $i + 1;$j < $count;$j++) {
if ($data[$i] > $data[$j]) {
$tmp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $tmp;
}
}
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
for ($j = $i + 1;$j < $count;$j++) {
if ($data[$i] < $data[$j]) {
$tmp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $tmp;
}
}
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 3
[6] => 2
[7] => 1
)
*/
- 直接插入排序
插入排序是依次将一个待排序元素插入已经排序的队列中的适当位置直到全部插入完成，直接插入排序是插入排序的一种。PHP实例如下：
// 由小到大直接插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
if ($data[$i-1] > $data[$i]) {
$tmp = $data[$i];
$j = $i;
while ($j > 0 && $data[$j - 1] > $tmp) {
$data[$j] = $data[$j - 1];
$j--;
}
$data[$j] = $tmp;
}
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小直接插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
if ($data[$i-1] < $data[$i]) {
$tmp = $data[$i];
$j = $i;
while ($j > 0 && $data[$j - 1] < $tmp) {
$data[$j] = $data[$j - 1];
$j--;
}
$data[$j] = $tmp;
}
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 2
[6] => 3
[7] => 1
)
*/
- 折半插入排序
折半插入排序是对直接插入排序的改进，将待排序元素与有序序列中间位置元素进行比较，根据比较结果确定待排元素继续比较的区间，直到找到合适的位置。PHP实例如下：
// 由小到大折半插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
$left = 0;
$right = $i - 1;
$tmp = $data[$i];
while ($left <= $right) {
$middle = ($left + $right) / 2;
if ($tmp < $data[$middle]) {
$right = $middle - 1;
} else {
$left = $middle + 1;
}
}
for ($j = $i;$j > $left;$j--) {
$data[$j] = $data[$j - 1];
}
$data[$j] = $tmp;
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小折半插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
$left = 0;
$right = $i - 1;
$tmp = $data[$i];
while ($left <= $right) {
$middle = ($left + $right) / 2;
if ($tmp > $data[$middle]) {
$right = $middle - 1;
} else {
$left = $middle + 1;
}
}
for ($j = $i;$j > $left;$j--) {
$data[$j] = $data[$j - 1];
}
$data[$j] = $tmp;
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 2
[6] => 3
[7] => 1
)
*/
- 快速排序
快速排序是对冒泡排序的改进，采用递归和分治的思想，将一个队列分成两个队列，其中一个队列中的元素都比第二个队列小，再对分割好的队列用同样的方式分割直到不能再分割为止，最后将分割出来的元素再按照分割后的顺序组合起来。PHP实例如下：
/*
* 由小到大快速排序
* @param array $param
* @return array
*/
function quickSortAsc($param) {
$count = count($param);
if ($count <= 1) {
return $param;
}
$base = $param[0];
$small = [];
$big = [];
for ($i = 1;$i < $count;$i++) {
if ($param[$i] > $base) {
$big[] = $param[$i];
} else {
$small[] = $param[$i];
}
}
return array_merge(quickSortAsc($small), [$base], quickSortAsc($big));
}
$data = [3, 5, 2, 34, 4, 7, 23, 1];
echo '<pre>';
print_r(quickSortAsc($data));
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
/*
* 由大到小快速排序
* @param array $param
* @return array
*/
function quickSortAsc($param) {
$count = count($param);
if ($count <= 1) {
return $param;
}
$base = $param[0];
$small = [];
$big = [];
for ($i = 1;$i < $count;$i++) {
if ($param[$i] > $base) {
$big[] = $param[$i];
} else {
$small[] = $param[$i];
}
}
return array_merge(quickSortAsc($big), [$base], quickSortAsc($small));
}
$data = [3, 5, 2, 34, 4, 7, 23, 1];
echo '<pre>';
print_r(quickSortAsc($data));
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 3
[6] => 2
[7] => 1
)
*/
- 计数排序
对于给定序列，直接将指定元素放在比它小的序列元素个数对应的序列位置上以完成排序的算法被成为计数排序。PHP实例如下：
// 由小到大计数排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$new_data = [];
for ($i = 0;$i < $count;$i++) {
$location = 0;
for ($j = 0;$j < $count;$j++) {
if ($data[$i] > $data[$j]) {
$location++;
}
}
while (isset($new_data[$location]) && $location < $count) {
$location++;
}
$new_data[$location] = $data[$i];
}
for ($i = 0;$i < $count;$i++) {
$data[$i] = $new_data[$i];
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小计数排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$new_data = [];
for ($i = 0;$i < $count;$i++) {
$location = 0;
for ($j = 0;$j < $count;$j++) {
if ($data[$i] < $data[$j]) {
$location++;
}
}
while (isset($new_data[$location]) && $location < $count) {
$location++;
}
$new_data[$location] = $data[$i];
}
for ($i = 0;$i < $count;$i++) {
$data[$i] = $new_data[$i];
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 2
[6] => 3
[7] => 1
)
*/
- 希尔排序
希尔排序是直接插入排序的改进版本，把队列下标按一定增量分组，对每组使用直接插入排序，随着增量减小每组的元素越来越多，当增量为1时整个队列是一组，算法结束。
// 由小到大希尔排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$random = 3;
$rank = 1;
while ($rank < $count / $random) {
$rank = $random * $rank + 1;
}
while ($rank >= 1) {
for ($i = $rank; $i < $count;$i++) {
for ($j = $i;$j >= $rank;$j -= $rank) {
if ($data[$j] < $data[$j - $rank]) {
$tmp = $data[$j];
$data[$j] = $data[$j - $rank];
$data[$j - $rank] = $tmp;
}
}
}
$rank = intval($rank / $random);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小希尔排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$random = 3;
$rank = 1;
while ($rank < $count / $random) {
$rank = $random * $rank + 1;
}
while ($rank >= 1) {
for ($i = $rank; $i < $count;$i++) {
for ($j = $i;$j >= $rank;$j -= $rank) {
if ($data[$j] > $data[$j - $rank]) {
$tmp = $data[$j];
$data[$j] = $data[$j - $rank];
$data[$j - $rank] = $tmp;
}
}
}
$rank = intval($rank / $random);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 3
[6] => 2
[7] => 1
)
*/
- 梳排序
梳排序是基于冒泡排序的，是对队列中固定距离处的元素进行比较和交换。PHP实例如下：
// 由小到大梳排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$step = intval($count / 1.4);
while ($step >= 1) {
for ($i = 0; $i < $count;$i++) {
if ($step + $i < $count && $data[$i] > $data[$step + $i]) {
$tmp = $data[$i];
$data[$i] = $data[$i + $step];
$data[$i + $step] = $tmp;
}
if ($step + $i >= $count) {
break;
}
}
$step = intval($step / 1.4);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 4
[3] => 3
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小梳排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$step = intval($count / 1.4);
while ($step >= 1) {
for ($i = 0; $i < $count;$i++) {
if ($step + $i < $count && $data[$i] < $data[$step + $i]) {
$tmp = $data[$i];
$data[$i] = $data[$i + $step];
$data[$i + $step] = $tmp;
}
if ($step + $i >= $count) {
break;
}
}
$step = intval($step / 1.4);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 3
[6] => 2
[7] => 1
)
*/
- 选择排序
选择排序依次访问未排序队列部分并找出最小（或最大）的元素，将找到的元素放在未排序队列的最前面指导排序完成。PHP实例如下：
// 由小到大选择排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
$index = $i;
for ($j = $i + 1; $j < $count;$j++) {
if ($data[$index] > $data[$j]) {
$index = $j;
}
}
if ($index != $i) {
$tmp = $data[$index];
$data[$index] = $data[$i];
$data[$i] = $tmp;
}
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 7
[6] => 23
[7] => 34
)
*/
// 由大到小选择排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
$index = $i;
for ($j = $i + 1; $j < $count;$j++) {
if ($data[$index] < $data[$j]) {
$index = $j;
}
}
if ($index != $i) {
$tmp = $data[$index];
$data[$index] = $data[$i];
$data[$i] = $tmp;
}
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
[0] => 34
[1] => 23
[2] => 7
[3] => 5
[4] => 4
[5] => 3
[6] => 2
[7] => 1
)
*/
本文首发于公众号：programmer_cc，转载请注明出处。
微信公众号.jpg
