php衰减算法(php数据结构)

admin

作者

作为一名合格php衰减算法的PHPer怎么能不接触到算法这个高大上的东西了php衰减算法，今天就来针对初学者来说一说最基础的4种排序算法：冒泡排序、选择排序、插入排序、快速排序（分区排序）。

冒牌排序

核心思想：比较相邻两个元素的大小，如果左边大于右边，则调换两个元素的位置；

缺点：需要将数组中的每一个元素都进行对比，耗时较长

$array = [5,10,3,4,2,8,7,9,11];$length = count($array);//第一层控制循环的次数，元素有多少个就需要循坏多少次for ($i = 1; $i < $length; $i++) { //第二层循环比较相邻元素的大小，调换位置 for ($j = 0; $j < $length - $i; $j++) { if ($array[$j] > $array[$j + 1]) { $tmp = $array[$j + 1]; //临时保存,替换两者位置 $array[$j + 1] = $array[$j]; $array[$j] = $tmp; } }}return $array;

选择排序

核心思想：取后一位元素与当前元素对比，然后将小的元素插入到最前位置

$array = [5,10,3,4,2,8,7,9,11];$length = count($array);//第一层控制循环的次数，元素有多少个就需要循坏多少次 for ($i = 0; $i < $length - 1; $i++) { $p = $i; //假设当前元素是最小元素的下标; //第二层循环从下一个元素开始比较 //注意这里的开始位置是从基准元素的下一个位置开始的 //可以认为前面的元素是已经排序完成了 for ($j = $i + 1; $j < $length; $j++) { //找到更小的元素下标 if ($array[$p] > $array[$j]) { $p = $j; } } //如果最小元素不是之前假设的元素,则调换位置 if ($p != $i) { $tmp = $array[$p]; $array[$p] = $array[$i]; $array[$i] = $tmp; } }return $array;

插入排序

核心思想：每次循环中，从下一个元素开始比较，然后将最小的元素插入到数组的最前面(但是为了更好的性能，我们通常采用替换位置的 *** 来将最小元素位移到数组的前面)

$array = [5,10,3,4,2,8,7,9,11];$length = count($array);//第一层控制循环的次数，元素有多少个就需要循坏多少次 for ($i = 1; $i < $length; $i++) { $tmp = $array[$i]; //记录当前基准元素 //从基准元素的下一个元素开始比较 for ($j = $i - 1; $j >= 0; $j--) { //如果下一个元素比当前基准元素要小则调换位置 if ($tmp < $array[$j]) { $array[$j + 1] = $array[$j]; $array[$j] = $tmp; } else { break; } } }return $array;

快速排序

核心思想：取任意元素为基准，然后二分递归一直执行，每次都是小的左边，大的右边。最后将结果合并

$array = [5,10,3,4,2,8,7,9,11];//如果不是数组则终止执行 if (!is_array($array)) return false; $length = count($array); //如果数组元素小于2个则终止执行 if ($length <= 1) return $array; $left = $right = []; //任意取一个元素作为基准元素 //将小于该基准的元素存放进左边 //将大于该基准的元素存放进右边 for ($i = 1; $i < $length; $i++) { if ($array[$i] > $array[0]) { $right[] = $array[$i]; } else { $left[] = $array[$i]; } } //递归执行 $left = quick_sort($left); $right = quick_sort($right); //将结果合并 return array_merge($left, [$array[0]], $right);

最后总结

经测试，四种 *** 中快速排序的性能最高。数组取10000个元素，然后分别执行消耗的时间如图所示