常见的排序算法

冒泡排序

将数组中的相邻元素的比较和交换来把小的数交换到最前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//冒泡排序
function maopao($num)
{
for ($i = 0; $i < count($num); $i++) {
for ($j = 0; $j < count($num) - $i - 1; $j++) {
if ($num[$j] > $num[$j + 1]) {
list($num[$j],$num[$j+1]) = [$num[$j+1],$num[$j]];
//$tmp = $num[$j + 1];
//$num[$j + 1] = $num[$j];
//$num[$j] = $tmp;
}
}
}
return $num;
}

选择排序

先找出最小的一个数。放到最前面.

选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子,对5,3,8,6,4这个无序序列进行简单选择排序,首先要选择5以外的最小数来和5交换,也就是选择3和5交换,一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换,最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了最小数的前提下才进行交换,大大减少了交换的次数。选择排序的时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function check_array($arr)
{
$count = count($arr);
for ($i = 0; $i < $count; $i++) {
$min = $i;
for ($j = $i + 1; $j < $count; $j++) {
if ($arr[$min] > $arr[$j]) {
$min = $j;
}
}
if ($min != $i) {
list($arr[$min], $arr[$i]) = [$arr[$i],$arr[$min]];
//$tem = $arr[$min];
//$arr[$min] = $arr[$i];
//$arr[$i] = $tem;
}
}
return $arr;
}

插入排序

插入排序类似玩儿扑克牌时候的理牌,将拿到的牌插入到正确的位置中去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort($arr)
{
$count = count($arr);
for ($i = 1; $i < $count; $i++) {
$key = $i-1;
$val = $arr[$i];
while ($val >= 0 && $arr[$key] > $val) {
$arr[$key + 1] = $arr[$key];
$key--;
}
$arr[$key + 1] = $val;
}

return $arr;
}

快速排序

快速排序是比较和交换小数和大数,这样一来不仅把小数冒泡到上面同时也把大数沉到下面。选择一个数,将小于这个数的数放入左边数组、大于这个数的放入右边数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//简易排序排序、不是正确的快速排序!!
function qsort($arr)
{
$count = count($arr);
//这一步不能少!!!!
if($count <= 1)
{
return $arr;
}
$midlle = $arr[0];
$left = $right = [];
for ($i = 1; $i < $count; $i++) {
($arr[$i] < $midlle) ? $left[] = $arr[$i] : $right[] = $arr[$i];
}
$left = qsort($left);
$right = qsort($right);

return array_merge($left, [$midlle], $right);
}

快速排序:

通过数组引用改变数组内元素值、返回原数组

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
32
33
34
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function Partition(array &$arr,$low,$high){
$pivot = $arr[$low]; //选取子数组第一个元素作为枢轴
while($low < $high){ //从数组的两端交替向中间扫描
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$low,$high); //终于遇到一个比$pivot小的数,将其放到数组低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$low,$high); //终于遇到一个比$pivot大的数,将其放到数组高端
}
return $low; //返回high也行,毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
if($low < $high){
$pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二,算出枢轴值
QSort($arr,$low,$pivot - 1); //对低子表进行递归排序
QSort($arr,$pivot + 1,$high); //对高子表进行递归排序
}
}

//快速排序入口
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$low,$high);
}

参考资料

https://blog.csdn.net/baidu_30000217/article/details/53311840

https://github.com/francistao/LearningNotes/blob/master/Part3/Algorithm/Sort/%E9%9D%A2%E8%AF%95%E4%B8%AD%E7%9A%84%2010%20%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93.md