常见的四种排序算法

对下面的数据进行排序


$arr = [3, 5, 2, 4, 6];

冒泡排序

  • 比较相邻的两个元素。如果第一个比第二个大,就交换他们两个
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

优点:稳定

缺点:慢,每次只能移动相邻两个数据

实现:


function bubbleSort(array &$arr): void { $num = count($arr); if ($num <= 1) { return; } for ($i = 0; $i < $num; $i++) { for ($j = 0; $j < $num - $i - 1; $j++) { if ($arr[$j] < $arr[$j + 1]) { $temp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $temp; } } } } /******************************/ print_r($arr); bubbleSort($arr); print_r($arr); /* 输出: Array ( [0] => 3 [1] => 5 [2] => 2 [3] => 4 [4] => 6 ) Array ( [0] => 6 [1] => 5 [2] => 4 [3] => 3 [4] => 2 ) */

快速排序

  • 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行

优点:极快,数据移动少.

缺点:不稳定


function quickSort(array $arr): array { $num = count($arr); if ($num <= 1) { return $arr; } $temp = $arr[0]; $leftArr = []; $rightArr = []; for ($i = 1; $i < $num; $i++) { if ($temp < $arr[$i]) { $leftArr[] = $arr[$i]; } else { $rightArr[] = $arr[$i]; } } $leftArr = quickSort($leftArr); $rightArr = quickSort($rightArr); return array_merge($leftArr, [$temp], $rightArr); } var_dump($arr, quickSort($arr)); /* 输出: Array ( [0] => 3 [1] => 5 [2] => 2 [3] => 4 [4] => 6 ) Array ( [0] => 6 [1] => 5 [2] => 4 [3] => 3 [4] => 2 ) */

选择排序

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

优点:数据移动次数已知为(n-1)次

缺点:比较次数多


function selectSort(array &$arr): void { $num = count($arr); if ($num <= 1) { return; } for ($i = 0; $i < $num - 1; $i++) { $index = $i; for ($j = $i + 1; $j < $num; $j++) { if ($arr[$index] > $arr[$j]) { $index = $j; } if ($index != $i) { $temp = $arr[$index]; $arr[$index] = $arr[$i]; $arr[$i] = $temp; } } } } print_r($arr); selectSort($arr); print_r($arr); /* 输出: Array ( [0] => 3 [1] => 5 [2] => 2 [3] => 4 [4] => 6 ) Array ( [0] => 2 [1] => 3 [2] => 5 [3] => 4 [4] => 6 ) */

插入排序

  • 每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

优点:稳定,快

缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候


function insertSort(array &$arr): void { $num = count($arr); if ($num <= 1) { return; } for ($i = 1; $i < $num; $i++) { $temp = $arr[$i]; for ($j = $i - 1; $j >= 0; $j--) { if ($temp < $arr[$j]) { $arr[$j + 1] = $arr[$j]; $arr[$j] = $temp; } else { break; } } } } print_r($arr); insertSort($arr); print_r($arr); /* 输出: Array ( [0] => 3 [1] => 5 [2] => 2 [3] => 4 [4] => 6 ) Array ( [0] => 2 [1] => 3 [2] => 5 [3] => 4 [4] => 6 ) */

希尔排序

归并排序

堆排序

计数排序

桶排序

基数排序

鲁ICP备16017569号-2