Laravel学习笔记之冒泡、快速、选择和插入排序(持续更新)

2016-06-23 10:30:00

说明：本文是对个人学习冒泡、快速、选择和插入排序的小总结。面试经常问这些东西，虽然不知道为啥老爱问这些，该问的又不问。不管咋样，个人学习MySQL时有关索引就用到快速排序，索引也是以B+Tree数据结构保存的(Innodb存储引擎)，所以基本功还是很重要的嘛。

快速排序

个人实验发现，快速排序在这四个排序当中似乎是最快的，看下图比较直观：

看下代码吧：

arrayQuickSort($left);        $right = $this->arrayQuickSort($right);        return array_merge($left, [$mid], $right);    }}$arr       = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];$arr2      = array_rand(range(1, 1000), 500);shuffle($arr2);$quickSort = new QuickSort();$time1     = microtime(true);//$quickArr  = $quickSort->arrayQuickSort($arr);$quickArr  = $quickSort->arrayQuickSort($arr2);//11.8780136108ms$time2     = microtime(true);//var_dump($quickArr);echo (($time2 - $time1)*1000).'ms'.PHP_EOL;

实验快速排序，排序随机的500个数只要11ms左右，还挺快。

冒泡排序

冒泡排序效率就比较差了，看图比较直观它的原理：

看代码吧：

 $data[$j+1]){                    $this->swap($data[$j], $data[$j+1]);                }            }        }        return $data;    }    /      * 字符串排序也和数组一样,字符串数组形式访问字符     * @param string|string $str     * @return string     */    public function stringBubbleSort(string $str)    {        $count = strlen($str);        for($i=0; $i $str[$j+1]){                    $this->swap($str[$j], $str[$j+1]);                }            }        }        return $str;    }    /      * 交换变量值     * @param $var1     * @param $var2     */    public function swap(&$var1, &$var2)    {        $tmp  = $var1;        $var1 = $var2;        $var2 = $tmp;    }}$arr   = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];$str   = 'SegmentFault';$arr2  = array_rand(range(1, 1000), 500);shuffle($arr2);$sort  = new BubbleSort();$time1 = microtime(true);//$bubbleArr = $sort->arrayBubbleSort($arr);$bubbleArr = $sort->arrayBubbleSort($arr2);//316.018104553ms$time2 = microtime(true);//var_dump($bubbleArr);echo (($time2 - $time1)*1000).'ms'.PHP_EOL;

实验冒泡排序，排序随机的500个数需要316ms左右，慢的不行。

插入排序

插入排序个人觉得就像是玩扑克，牌桌上n张牌，一张张抓过来，然后新牌根据手上的m张牌依次比较，找到对应位置。看图比较直观：

看代码吧：

0; $j--){                if($data[$j] > $data[$j-1]){                    break;                }                $this->swap($data[$j-1], $data[$j]);            }        }        return $data;    }    /      * 交换变量值     * @param $var1     * @param $var2     */    public function swap(&$var1, &$var2)    {        $tmp  = $var1;        $var1 = $var2;        $var2 = $tmp;    }}$arr       = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];$arr2      = array_rand(range(1, 1000), 500);shuffle($arr2);$insert    = new InsertSort();$time1     = microtime(true);//$insertArr = $insert->arrayInsertSort($arr);$insertArr = $insert->arrayInsertSort($arr2);//315.321922302ms$time2     = microtime(true);//var_dump($insertArr);echo (($time2 - $time1)*1000).'ms'.PHP_EOL;

实验插入排序，排序随机的500个数需要315ms左右，和冒泡排序差不多速度。

选择排序

选择排序速度还行，看图：

看代码吧：

 $data[$j]){                    $min = $j;                }            }            if($min != $i){                $this->swap($data[$min], $data[$i]);            }        }        return $data;    }    /      * 交换变量值     * @param $var1     * @param $var2     */    public function swap(&$var1, &$var2)    {        $tmp  = $var1;        $var1 = $var2;        $var2 = $tmp;    }}$arr2      = array_rand(range(1, 1000), 500);shuffle($arr2);$arr       = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];$select    = new SelectSort();$time1     = microtime(true);//$selectArr = $select->arraySelectSort($arr);$selectArr = $select->arraySelectSort($arr2);//44.0230369568ms$time2 = microtime(true);//var_dump($selectArr);echo (($time2 - $time1)*1000).'ms'.PHP_EOL;

实验选择排序，排序随机的500个数需要44ms左右，速度还行。

总结：排序和查找是永恒主题。扎实下基本功，会继续学习相关排序和查找算法，到时见。

关键字：php, 冒泡排序, 快速排序, 插入排序

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击举报进行投诉反馈！