了解如何快速使用程序进行排序，对于程序运行速度的提升，对于程序的优化有着很关键的作用，今天先来总结一下几种最基础也是最经典的排序算法。
一、冒泡排序
依次比较相邻两个元素大小，将小的的放前面，大的放后面，直至最后两个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| <?php
namespace BubbleSort;
function bubbleSort($array){
if (!is_array($array)){
return false;
}
if (count($array) <2) return $array;
$length = count($array);
for ($i = 0;$i<$length-1; $i++){
for ($j = 0; $j<$length-$i-1;$j++){
if ($array[$j] >$array[$j+1]) {
$temp = $array[$j];
$array[$j] = $array[$j+1];
$array[$j+1] = $temp;
}
}
}
return $array;
}
$arr = [2,6,2,8,2,34,5,9,2341,23];
var_dump(bubbleSort($arr));
?>
|
二、快速排序
- 从序列当中选择一个基准数，一般取第一个
- 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧。
- 重复前两个步骤，直到所有子集当中只有一个元素为止。
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
29
30
31
| <?php
namespace QuickSort;
function quickSort($arr){
if(!is_array($arr)) return false;
$length = count($arr);
if ($length <=1) return $arr;
$left = $right = array();
for ($i=1;$i<$length;$i++)
{
if ($arr[$i] < $arr[0])
{
$left[] = $arr[$i];
}
else
{
$right[] = $arr[$i];
}
}
$left = quickSort($left);
$right = quickSort($right);
return array_merge($left,[$arr[0]],$right);
}
$arr = [34,56,8,79,12,3];
var_dump(quick_sort($arr));
?>
|
三、插入排序
每次从无序列表中取出第一个元素，把他插入到有序表中的合适位置，使有序表仍然有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| <?php
namespace InsertSort;
function insertSort($arr){
if (count($arr)<2) return $arr;
if (!is_array($arr)) return false;
$length = count($arr);
for ($p = 1; $p<$length; $p++){
$temp = $arr[$p];
for ($i = $p ; $i>0&& $arr[$i-1]>$temp;$i--){
$arr[$i] = $arr[$i-1];
}
$arr[$i] = $temp;
}
return $arr;
}
$arr = [34,56,8,79,12,3];
var_dump(insertSort($arr));
?>
|
四、选择排序
每次从待排序的元素中的第一个元素，设为最小值，再遍历每一个没有排序的元素，如果元素小于现在的最小值，就将这个元素设为最小值和第一个没有排过序的元素交换位置。
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
| <?php
namespace SelectSort;
function selectSort($arr){
$length = count($arr);
for ($i =0;$i<$length;$i++){
$min = $i;
for ($j = $i+1; $j<$length;$j++){
if ($arr[$j]<$arr[$min]){
$min = $j;
}
}
if ($min != $i) {
list($arr[$i], $arr[$min]) = [$arr[$min], $arr[$i]];
}
}
return $arr;
}
$arr = [34,56,8,79,12,3];
var_dump(selectSort($arr));
?>
|