[TOC] :-:  # 冒泡排序 冒泡排序又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误则交换两个元素，走访数列的工作是重复的进行直到没有需要交换的，也就是说该数列已经排序完成，这个算法名字的由来是因为**越小的元素会经由交换慢慢"浮"到数列的顶端**。 1. 从头开始比较两个元素,如果顺序错误则交换两个元素，循环比较数组直到没有需要交换的 2. 1和2、2和3… 2 3. 里面的循环执行完第一轮，最末尾的元素就是最大的元素，外层循环走完，数组也算排序完成 ~~~php function bubbleSort($arr) { $count = count($arr); for ($i = 0; $i < $count- 1; $i++) { for ($j = 0; $j < $count - $i -1; $j++) { if ($arr[$j] < $arr[$j + 1]) { $tmp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $tmp; } } } return $arr; } ~~~ # 快速排序 快速排序，又称分区交换排序，简称快排，它采用了一种分治的策略，通常称其为分治法，把一个序列分为较小和较大的2个子序列，然后递归的排序两个子系列。 1. 从数列中挑出一个数作为**基准元素(pivot)**。通常选择第一个或最后一个元素。 2. 扫描数列，**以基准元素为比较对象，把数列分成两个区**。规则是：小的移动到基准元素前面，大的移到后面，相等的前后都可以。分区完成之后，基准元素就处于数列的中间位置。 3. 然后再用同样的方法，**递归地排序划分的两部分**。 ~~~php function quickSort($arr) { $count = count($arr); //先设定结束条件，判断是否需要继续进行 if ($count <= 1) { return $arr; } //选择第一个元素作为基准元素 $pivot = $arr[0]; //初始化左右数组,左小右大 $left_arr = $right_arr = array(); //遍历除基准元素外的所有元素，按照大小关系放入左右数组内 for($i = 1; $i < $count; $i++) { if ($arr[$i] < $pivot) { $left_arr[] = $arr[$i]; } else { $right_arr[] = $arr[$i]; } } //再分别对左右数组进行相同的排序 $left = quickSort($left_arr); $right = quickSort($right_arr); return array_merge($left, array($pivot), $right); } ~~~ # 插入排序 插入排序是一种简单直观的排序算法。 插入排序的工作原理是：**将需要排序的数，与前面已经排好序的数据从后往前进行比较，使其插入到相应的位置。** 插入排序在实现上，通常采用in-place排序，即只需用到O(1)的额外空间的排序。 因而，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 1. 从第一个元素开始，该元素可以认为已经被排序； 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描； 3. 如果以排序的元素大于新元素，将该元素移到下一位置； 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置； 5. 将新元素插入到该位置中； 6. 重复步骤2。 ~~~php funciton insertSort($arr) { for ($i = 1; $i < count($arr); $i++) { $tmp = $arr[$i]; for ($j = $i - 1; $j >=0; $j--) { if ($tmp < $arr[$j]) { $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; } else { break; } } } return $arr; } ~~~ # 选择排序 选择排序是一种简单直观的排序算法。首先在未排序序列中找到最大（小）元素，存放到排序序列的起始位置，然后在从剩余的未排序的元素中据需寻找最大（小）元素，然后放到已排序的序列的末尾，一次类推，知道所有元素均排序完毕。 1. 首先，在序列中找到最小元素，存放到排序序列的起始位置； 2. 接着，从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。 3. 重复第二步，直到所有元素均排序完毕。 ~~~php function selectSort($arr) { $count = count($arr); for ($i = 0; $i < $count; $i++) { $p = $i; for ($j = $i + 1; $j < $count; $j ++) { if ($arr[$p] > $arr[$j]) { $p = $j; } } $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } return $arr; } ~~~ # 归并排序 归并排序是建立在归并操作上的一种有效的排序算法。 归并排序将待排序的序列分成若干组，保证每组都有序，然后再进行合并排序，最终使整个序列有序。 该算法是采用分治法的一个非常典型的应用。 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列； 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4. 重复步骤3直到某一指针达到序列尾 5. 将另一序列剩下的所有元素直接复制到合并序列尾 ~~~php function mergeSort($arr) { $count = count($arr); if ($count <= 1) { return $arr; } $left = merge_sort(array_slice($arr, 0, floor($n / 2))); $right = merge_sort(array_slice($arr, 0, floor($n / 2))); $arr = merge($left, $right); return $arr; } function merge($left, $right) { $arr = []; $i = $j = 0; while ($i < count($left) && $j < count($right)) { if ($left[$i] < $right[$j]) { $arr[] = $left[$i]; $i++; } else { $arr[] = $right[$j]; $j++; } $arr = array_merge($arr, array_slice($left, $i)); $arr = array_merge($arr, array_slice($right, $j)); return $arr; } } ~~~ # 希尔排序 希尔排序，也称**递减增量**排序算法，是插入排序的一种更高效的改进版本。 但希尔排序是非稳定排序算法 希尔排序是基于插入排序的以下两点性质而提出改进方法的： * 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 * 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位 1. 先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序 2. 待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 ~~~php function shellSort($arr) { $count = count($arr); $step = 2; $gap = intval($count / $step); while ($gap > 0) { for ($gi = 0; $gi < $gap; $gi++) { for ($i = $gi; $i < $count; $i += $gap) { $key = $arr[$i]; for ($j = $i - $gap; $j >= 0 && $arr[$j] > $key; $j -= $gap) { $arr[$j + $gap] = $arr[$j]; $arr[$j] = $key; } } } $gap = intval($gap / $step); } return $arr; } ~~~ # 堆排序 堆排序是指利用堆这种数据结构所设计的一种排序算法。 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 堆排序的平均时间复杂度为Ο(nlogn) 。 1. 创建一个堆`H[0..n-1]`； 2. 把堆首（最大值）和堆尾互换； 3. 把堆的尺寸缩小`1`，并调用`shift_down(0)`，目的是把新的数组顶端数据调整到相应位置； 4.  重复步骤`2`，直到堆的尺寸为`1`。 ~~~php /** * 堆排序 * * @param array $lists * @return array */ function heap_sort(array $lists) { $n = count($lists); build_heap($lists); while (--$n) { $val = $lists[0]; $lists[0] = $lists[$n]; $lists[$n] = $val; heap_adjust($lists, 0, $n); //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL; } return $lists; } function build_heap(array &$lists) { $n = count($lists) - 1; for ($i = floor(($n - 1) / 2); $i >= 0; $i--) { heap_adjust($lists, $i, $n + 1); //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL; } //echo "build ok: " . implode(', ', $lists) . PHP_EOL; } function heap_adjust(array &$lists, $i, $num) { if ($i > $num / 2) { return; } $key = $i; $leftChild = $i * 2 + 1; $rightChild = $i * 2 + 2; if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) { $key = $leftChild; } if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) { $key = $rightChild; } if ($key != $i) { $val = $lists[$i]; $lists[$i] = $lists[$key]; $lists[$key] = $val; heap_adjust($lists, $key, $num); } } ~~~