介绍三种排序算法
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。
简单解释
首先默认序列的第一个元素为最小值A,然后从剩下的序列里面,选取最小值B,如果B
code
- function selectSort($arr) {
- $len = count($arr);
- for ($i = 0; $i < $len - 1; $i++) {
- // 默认第一个是最小值
- $min = $i;
- // 注意这里是从$i + 1 开始遍历剩余的元素,选出最小值
- for ($n = $i + 1; $n < $len; $n++) {
- if ($arr[$n] < $arr[$min]) {
- $min = $n;
- }
- }
- // 如果最小值不是当前默认的最小值,那么进行替换
- if ($min != $i) {
- $t = $arr[$i];
- $arr[$i] = $arr[$min];
- $arr[$min] = $t;
- }
- }
- return $arr;
- }
比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
简单解释
要比较N轮,每轮都要比较N-当前轮次的次数, 每次都会选出一个最大值放到后面(有点抽象)
代码
- function bubbleSort($arr) {
- $len = count($arr);
- // 这里比较N次
- for ($i = 0; $i < $len - 1; $i++) {
- // 每次比较实际上都要-$i,因为每次比较结束后最后一个值就不用参与下次比较了
- for ($n = 0; $n < $len - 1 - $i; $n++) {
- if ($arr[$n] > $arr[$n + 1]) {
- $t = $arr[$n];
- $arr[$n] = $arr[$n + 1];
- $arr[$n + 1] = $t;
- }
- }
- }
- return $arr;
- }
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
简单解释
这个真的更抽象,因为,就是将小的放一边,大的放一边,然后递归出来
code
- function quickSort($arr) {
- $len = count($arr);
- // 因为是递归,所以如果最后的数组可能是空的也可能是1个,那么就没有可比较的了,直接返回
- if ($len <= 1) {
- return $arr;
- }
- $base = $min = $max = [];
- $base_item = $arr[0];
- for ($i = 0; $i < $len; $i++) {
- if ($arr[$i] < $base_item) {
- $min[] = $arr[$i];
- }
- elseif($arr[$i] > $base_item) {
- $max[] = $arr[$i];
- } else {
- $base[] = $arr[$i];
- }
- }
- $min = quickSort($min);
- $max = quickSort($max);
- // 每次构造新的序列
- return array_merge($min, $base, $max);
- }
这三个排序算法的时间复杂度是不一样的,我们来测试下性能。我们用下面代码来生成散列数组。
- $arr
- =
- range
- (0,
- $argv
- [1]);
- shuffle(
- $arr
- );
然后执行上面三个方法
- $time = execTime();
- // 快速排序
- quickSort($arr);
- $time = execTime($time);
- // 选择排序
- selectSort($arr);
- $time = execTime($time);
- // 冒泡排序
- bubbleSort($arr);
- $time = execTime($time);
- // 这个是计算毫秒耗时的方法
- function
- execTime
- ($microTime = 0)
- {
- $microTime && var_dump(microtime(true)*1000 - $microTime);
- return microtime(true)*1000;
- }
看下执行结果,果然最快的是快速排序
- php sort_practice.php 10
- float(0.0419921875)
- float(0.011962890625)
- float(0.011962890625)
- php sort_practice.php 100
- float(0.30908203125)
- float(0.396240234375)
- float(0.779052734375)
- php sort_practice.php 200
- float(0.687744140625)
- float(1.93994140625)
- float(3.37890625)
- php sort_practice.php 300
- float(0.85400390625)
- float(3.222900390625)
- float(8.123046875)
- php sort_practice.php 400
- float(1.23193359375)
- float(5.857177734375)
- float(11.824951171875)
- php sort_practice.php 500
- float(1.559814453125)
- float(8.73291015625)
- float(21.15087890625)
- php sort_practice.php 600
- float(1.70703125)
- float(14.300048828125)
- float(30.343994140625)
- php sort_practice.php 700
- float(2.265869140625)
- float(18.0390625)
- float(41.654052734375)
- php sort_practice.php 800
- float(2.581298828125)
- float(24.72998046875)
- float(53.56005859375)
- php sort_practice.php 900
- float(2.682861328125)
- float(31.9560546875)
- float(65.988037109375)
- php sort_practice.php 1000
- float(3.18701171875)
- float(36.010986328125)
- float(78.216064453125)
- php sort_practice.php 2000
- float(6.450927734375)
- float(151.62475585938)
- float(313.64624023438)
- php sort_practice.php 3000
- float(11.026123046875)
- float(362.6640625)
- float(721.11572265625)
- php sort_practice.php 4000
- float(15.346923828125)
- float(667.11791992188)
- float(1314.2221679688)
- php sort_practice.php 5000
- float(20.559814453125)
- float(1029.8937988281)
- float(2057.3466796875)
- php sort_practice.php 6000
- float(27.767822265625)
- float(1534.2431640625)
- float(2917.7407226562)
- php sort_practice.php 7000
- float(33.481201171875)
- float(2083.5861816406)
- float(3984.7060546875)
- php sort_practice.php 8000
- float(38.852783203125)
- float(2606.0270996094)
- float(5157.6708984375)
- php sort_practice.php 9000
- float(42.02587890625)
- float(3436.4509277344)
- float(6638.451171875)
- php sort_practice.php 10000
- float(45.932861328125)
- float(4640.3000488281)
- float(8474.2751464844)
再写一个经典搜索
先从中间开始找,递归类似快速排序
- $arr = range(0, $argv[1]);
- $value = mt_rand(0, count($arr));
- var_dump($value);
- function binSearch($value, $arr) {
- if (!$arr) {
- return false;
- }
- $sign = floor(count($arr) / 2);
- $middle = $arr[$sign];
- if ($middle == $value) {
- var_dump($middle);
- } else {
- binSearch($value, array_slice($arr, 0, $sign));
- binSearch($value, array_slice($arr, $sign + 1));
- }
- }
- binSearch($value, $arr);
来源: https://juejin.im/entry/59f6e926f265da430405e795