排序 · 前端

# [八种排序](https://www.cnblogs.com/lichihua/diary/2018/08/16/9484919.html) 1\. 冒泡排序思路分析：在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。代码实现： ~~~ /** * 冒泡排序 * @param array $arr * @return array */ function bubbleSort($arr) { // 数组长度 $length = count($arr); // 正向遍历数组 for ($i = 1; $i < $length; $i++) { // 反向遍历 for ($j = $length - 1; $j >= $i ; $j--) { // 相邻两个数比较 if ($arr[$j] < $arr[$j-1]) { // 暂存较小的数 $iTemp = $arr[$j-1]; // 较大的放前面 $arr[$j-1] = $arr[$j]; // 较小的放后面 $arr[$j] = $iTemp; } } } return $arr; } ~~~ 2.选择排序思路分析：在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。代码实现： ~~~ function xsort($arr){ $length=count($arr); for ($i=0; $i <$length-1 ; $i++) { for ($k=$i+1; $k <$length ; $k++) { //当前值arr[$i]与余下的比较 if ($arr[$i]>$arr[$k]) { $temp=$arr[$k]; $arr[$k]=$arr[$i]; $arr[$i]=$temp; } } } return $arr; } /** * 选择法排序 * @param array $arr * @return array */ function choiceSort($arr) { // 数组长度 $length = count($arr); // 遍历数组 for ($i = 0;$i < $length-1; $i++) { // 暂存当前值 $iTemp = $arr[$i]; // 暂存当前位置 $iPos = $i; // 遍历当前位置以后的数据 for ($j = $i + 1;$j < $length; $j++){ // 如果有小于当前值的 if ($arr[$j] < $iTemp) { // 暂存最小值 $iTemp = $arr[$j]; // 暂存位置 $iPos = $j; } } // 把当前值放到算好的位置 $arr[$iPos] = $arr[$i]; // 把当前值换成算好的值 $arr[$i] = $iTemp; } return $arr; } ~~~ 3.插入排序思路分析：在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。代码实现： ~~~ /** * 插入法排序 * @param array $arr * @return array */ function insertSort($arr){ $length = count($arr); // 遍历数组 for ($i = 1;$i < $length; $i++) { // 获得当前值 $iTemp = $arr[$i]; // 获得当前值的前一个位置 $iPos = $i - 1; // 如果当前值小于前一个值切未到数组开始位置 while (($iPos >= 0) && ($iTemp < $arr[$iPos])) { // 把前一个的值往后放一位 $arr[$iPos + 1] = $arr[$iPos]; // 位置递减 $iPos--; } $arr[$iPos+1] = $iTemp; } return $arr; } ~~~ 4.快速排序思路分析：选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。代码实现： ~~~ /** * 快速排序 * @param array $arr * @return array */ function quickSort($arr){ $length = count($arr); $l = $r = 0; $left = $right = array(); // 从索引的第二个开始遍历数组 for ($i = 1;$i < $length; $i++) { // 如果值小于索引1 if ($arr[$i] < $arr[0]) { // 装入左索引数组(小于索引1的数据) $left[] = $arr[$i]; $l++; } else { // 否则装入右索引中(大于索引1的数据) $right[] = $arr[$i]; $r++; // } } // 如果左索引有值则对左索引排序 if($l > 1) { $left = QuickSort($left); } // 排序后的数组 $new_arr = $left; // 将当前数组第一个放到最后 $new_arr[] = $arr[0]; // 如果又索引有值则对右索引排序 if ($r > 1) { $right = QuickSort($right); } // 根据右索引的长度再次增加数据 for($i = 0;$i < $r; $i++) { $new_arr[] = $right[$i]; } return $new_arr; } ~~~ 5.希尔排序思路分析：将数组按指定步长分隔成若干子序列，然后分别对子序列进行排序（在这是直接）代码实现： ~~~ /** * 希尔排序 * @param array $arr * @return array */ function shellSort($arr) { $len = count($arr); $k = floor($len/2); while($k > 0) { for($i = 0; $i < $k; $i++) { for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) { if($arr[$j] > $arr[$j+$k]) { $tmp = $arr[$j+$k]; $arr[$j+$k] = $arr[$j]; $arr[$j] = $tmp; } } } $k = floor($k/2); } return $arr; } ~~~ 6.堆排序思路分析：调整子堆的为大根堆的过程代码实现： ~~~ /** * 堆排序 * @param array &$arr 数组 * @param int $s 子堆的根的位置 * @param int $m 堆最后一个元素位置 * @return array */ function heapAdjust(&$arr, $s, $m) { $tmp = $arr[$s]; // 在调整为大根堆的过程中可能会影响左子堆或右子堆 // for循环的作用是要保证子堆也是大根堆 for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) { // 找到根节点的左右孩子中的最大者，然后用这个最大者与根节点比较， // 若大则进行调整，否则符合大根堆的特点跳出循环 if($j < $m && $arr[$j] < $arr[$j+1]) { $j++; } if($tmp >= $arr[$j] ) { break; } $arr[$s] = $arr[$j]; $s = $j; } $arr[$s] = $tmp; } /** * 堆排序 * @param array $arr 数组 * @return array */ function heapSort($arr) { $len = count($arr); // 依次从子堆开始调整堆为大根堆 for($i = floor($len/2-1); $i >= 0; $i--) { heapAdjust($arr, $i, $len-1); } // 依次把根节点调换至最后一个位置，再次调整堆为大根堆，找到次最大值， // 依次类推得到一个有序数组 for($n = $len-1; $n > 0; $n--) { $tmp = $arr[$n]; $arr[$n] = $arr[0]; $arr[0] = $tmp; heapAdjust($arr, 0, $n-1); } return $arr; } ~~~ 7.归并排序思路分析：这里实现的是两路归并(分别将有序的arr1\[s..m\]、arr1\[s..m\]、arr2\[m+1..n\]归并为有序的$arr2\[s..n\]) 代码实现： ~~~ /** * 归并排序 * @param array &$arr1 * @param array &$arr2 * @param int $s * @param int $m * @param int $n */ function Merge(&$arr1, &$arr2, $s, $m, $n) { for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) { if($arr1[$i]<$arr1[$j]) { $arr2[$k] = $arr1[$i++]; }else { $arr2[$k] = $arr1[$j++]; } } if($i <= $m) { for(; $i <= $m; $i++) { $arr2[$k++] = $arr1[$i]; } }else if($j <= $n) { for(; $j <= $n; $j++) { $arr2[$k++] = $arr1[$j]; } } } /** * 递归形式的两路归并 * @param array &$arr1 * @param array &$arr2 * @param int $s * @param int $t */ function MSort(&$arr1, &$arr2, $s, $t) { if($s == $t) { $arr2[$s] = $arr1[$s]; }else { $m = floor(($s+$t)/2); $tmp_arr = array(); MSort($arr1, $tmp_arr, $s, $m); MSort($arr1, $tmp_arr, $m+1, $t); Merge($tmp_arr, $arr2, $s, $m, $t); } } /** * 对一位数组$arr[0..n-1]中的元素进行两路归并 * @param array $arr * @return array */ function mergeSort($arr) { $len = count($arr); MSort($arr, $arr, 0, $len-1); return $arr; } ~~~ 8.交换法排序代码实现： ~~~ /** * 交换法排序 * @param array $arr * @return array */ function swapSort($arr){ $length = count($arr); // 遍历数组 for ($i = 0;$i < $length - 1; $i++) { // 获得当前索引的下一个索引 for ($j = $i + 1; $j < $length; $j++) { // 比较相邻两个的值大小 if ($arr[$j] < $arr[$i]) { // 暂存较小的数 $iTemp = $arr[$i]; // 较大的放前面 $arr[$i] = $arr[$j]; // 较小的放后面 $arr[$j] = $iTemp; } } } return $arr; } ~~~