logo头像

迪拜 ❤ 天空

实现四种基本排序算法

冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$arr = array(1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39);
function bubbleSort($arr) {
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
for ($k = 0; $k < $len - $i; $k++) {
if ($arr[$k] > $arr[$k + 1]) {
$tmp = $arr[$k + 1];
$arr[$k + 1] = $arr[$k];
$arr[$k] = $tmp
}
}
}
return $arr
}

选择排序

思路分析:在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectSort($arr) {
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
$p = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$p] > $arr[$j]) {
$p = $j
}
}
if ($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp
}
}
return $arr
}

插入排序

思路分析:在要排序的一组数中,假设前面的数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort($arr) {
$len = count($arr);
for ($i = 1, $i < $len; $i++) {
$tmp = $arr[$i];
for ($j = $i - 1; $j >= 0; $j--) {
if ($tmp < $arr[$j]) {
$arr[$j + 1] = $arr[$j];
$arr[$j] = $tmp
} else {
break
}
}
}
return $arr
}

快速排序

思路分析:选择一个基准元素,通常选择第一个元素或者最后一个元素。通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素。此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quickSort($arr) {
$length = count($arr);
if ($length <= 1) {
return $arr
}
$base_num = $arr[0];
$left_array = array();
$right_array = array();
for ($i = 1; $i < $length; $i++) {
if ($base_num > $arr[$i]) {
$left_array[] = $arr[$i]
} else {
$right_array[] = $arr[$i]
}
}
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
return array_merge($left_array, array($base_num), $right_array)
}

PHP内置的排序算法

  • sort()

    升序排列数组。value/key关联不保留
  • rsort()

    按反向/降序排序数组。index/key关联不保留
  • asort()

    在保持索引关联的同时排序数组
  • arsort()

    对数组进行反向排序并维护索引关联
  • ksort()

    按关键字排序数组。它保持数据相关性的关键。这对于关联数组是有用的
  • krsort()

    按顺序对数组按键排序
  • natsort()

    使用自然顺序算法对数组进行排序,并保持value/key关联
  • natcasesort()

    使用不区分大小写的“自然顺序”算法对数组进行排序,并保持value/key关联。
  • usort()

    使用用户定义的比较函数按值对数组进行排序,并且不维护value/key关联。第二个参数是用于比较的可调用函数
  • uksort()

    使用用户定义的比较函数按键对数组进行排序,并且不维护value/key关联。第二个参数是用于比较的可调用函数
  • uasort()

    使用用户定义的比较函数按值对数组进行排序,并且维护value/key关联。第二个参数是用于比较的可调用函数

评论系统未开启,无法评论!