[TOC] ## 排序算法 冒泡排序、直接插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序 ### **冒泡排序** * 两两相邻的数进行比较，反序则交换 * 时间复杂度：最坏O(n^2) ， 平均O(n^2) * 空间复杂度：O(1) ``` $arr = [3,8,1,5,2]; for($i = 0; $i < count($arr); $i++ ){ for($j = $i+1; $j < count($arr); $j++ ){ if($arr[$i] > $arr[$j]){ $temp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $temp; } } } ``` ### **直接插入排序** * 每次从无序表中取出第一个元素，插入到有序表中 * 时间复杂度：最坏O(n^2) ， 平均O(n^2) * 空间复杂度：O(1) ``` /** * 分成有序表和无序表 * 第一位为有序组，在左侧，其余则是无序组 * 剩下的依次和左侧进行比对插入 */ $arr = array(1,3,6,4,1,2); $count = count($arr); for($i = 1; $i < $count; $i++){ $temp = $arr[$i]; // 需要比较的值 for($j = $i-1; $j >= 0; $j--){ if($arr[$j] > $temp){ $arr[$j+1] = $arr[$j]; $arr[$j] = $temp; }else{ break; } } } ``` ### **希尔排序** * 按下标的一定增量分组，对每一组使用`直接插入排序`随着增量逐渐减少，每组包含的关键字越来越多，当增量减少至 1 时，整个序列恰好被分成一组，算法便终止。 * 时间复杂度：最坏O(n^2) ， 平均O(n*long2n) * 空间复杂度：O(1) ``` $arr = array(49,38,65,97,76,13,27,49,55,04); $count = count($arr); $inc = $count; //增量 do { //计算增量 $inc = ceil($inc / 2); for ($i = $inc; $i < $count; $i++) { $temp = $arr[$i]; //设置哨兵 //需将$temp插入有序增量子表 for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) { $arr[$j + $inc] = $arr[$j]; //记录后移 } //插入 $arr[$j + $inc] = $temp; } //增量为1时停止循环 } while ($inc > 1); ``` ### **选择排序** * 每次从数据中选择最小或最大的一个元素，放到序列的起始位置 * 时间复杂度：最坏O(n^2) ， 平均O(n^2) * 空间复杂度：O(1) ``` $arr = array(1,3,6,4,1,2); for ($i = 0; $i < count($arr); $i++) { $p = $i; //假设为最小 for ($k = $i+1; $k < count($arr); $k++) { if($arr[$p] < $arr[$k]){ //比对最小值 $p = $k; } } if($p != $i){ //位置不相等，进行替换 $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } } var_dump($arr);die; ``` ### **快速排序** * 通过一趟排序分成一大一小两组，然后分别对两组进行同样的排序，用递归完成 * 时间复杂度：最坏O(n^2) ， 平均O(nlong2n) * 空间复杂度：最差O(n)，平均O(log2n) ### **堆排序** * 按照大小在二叉树位置上排列，满足父节点大于等于子节点。如果根节点是最大的数叫大根堆，最小就叫小根堆 * 时间复杂度：最坏O(nlog2n) ， 平均O(nlong2n) * 空间复杂度：最差O(1) ### **归并排序** * 将两个或以上的有序表合并成一个新的有序表。 * 时间复杂度：最坏O(nlog2n) ， 平均O(nlong2n) * 空间复杂度：最差O(n) ## 查找算法 二分查找、顺序查找 ### **二分查找** * 从数组中间的元素开始，如果中间元素正好是查找的元素，搜索结束，如果大于或小于中间元素则在数组大于或者小于中间元素的那一半查找，直到找到或为空。 * 时间复杂度：最坏O(log2n) ， 平均O(long2n) * 空间复杂度：迭代O(1)、递归O(long2n) ### **顺序查找** * 按一定的顺序检查数组中每一个元素，直到找到为止。 * 时间复杂度：最坏O(n) ， 平均O(n) * 空间复杂度：O(1)