快速排序是由东尼·霍尔发展的一种排序算法。
在平均状况下,排序 n
个项目要Ο(n log n)
次比较。
在最坏状况下则需要Ο(n2)
次比较,但这种状况并不常见。
事实上,快速排序通常明显比其他Ο(n log n)
算法更快,因为它的内部循环可以在大部分的架构上,很有效率地被实现出来。
快速排序采用分治法实现排序,具体步骤:
递归的结束条件是数列的大小是0
或1
,也就是永远都已经被排序好了。
PHP代码实现:
function quickSort($arr) { // 先设定结束条件,判断是否需要继续进行 if(count($arr) <= 1) { return $arr; } // 选择第一个元素作为基准元素 $baseValue = $arr[0]; // 初始化小于基准元素的左数组 $leftArray = array(); // 初始化大于基准元素的右数组 $rightArray = array(); // 遍历除基准元素外的所有元素,按照大小关系放入左右数组内 array_shift($arr); foreach ($arr as $value) { if ($value < $baseValue) { $leftArray[] = $value; } else { $rightArray[] = $value; } } // 再分别对左右数组进行相同的排序 $leftArray = quickSort($leftArray); $rightArray = quickSort($rightArray); // 合并基准元素和左右数组 return array_merge($leftArray, array($baseValue), $rightArray); }
冒泡排序是一种简单的排序算法。
算法重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
走访数列的工作重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。
因为排序过程让较大的数往下沉,较小的往上冒,故而叫冒泡法。
算法步骤:
PHP代码实现:
function bubbleSort($arr) { $len = count($arr); for($i = 1; $i < $len; $i++) { for($k = 0; $k < $len - $i; $k++) { if($arr[$k] > $arr[$k + 1]) { $tmp = $arr[$k + 1]; $arr[$k + 1] = $arr[$k]; $arr[$k] = $tmp; } } } return $arr; }
插入排序是一种简单直观的排序算法。
插入排序的工作原理是:将需要排序的数,与前面已经排好序的数据从后往前进行比较,使其插入到相应的位置。
插入排序在实现上,通常采用in-place排序,即只需用到O(1)
的额外空间的排序。
因而,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
算法步骤:
PHP代码实现:
function insertSort($arr) { $len = count($arr); for ($i = 1; $i < $len; $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; }
选择排序是一种简单直观的排序算法。
算法步骤:
PHP代码实现:
function selectSort($arr) { $len = count($arr); for ($i = 0; $i < $len; $i++) { $p = $i; for ($j = $i + 1; $j < $len; $j++) { if ($arr[$p] > $arr[$j]) { $p = $j; } } $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } return $arr; }
归并排序是建立在归并操作上的一种有效的排序算法。
归并排序将待排序的序列分成若干组,保证每组都有序,然后再进行合并排序,最终使整个序列有序。
该算法是采用分治法的一个非常典型的应用。
算法步骤:
排序效果:
PHP实现代码:
/** * 归并排序 * * @param array $lists * @return array */ function merge_sort(array $lists) { $n = count($lists); if ($n <= 1) { return $lists; } $left = merge_sort(array_slice($lists, 0, floor($n / 2))); $right = merge_sort(array_slice($lists, floor($n / 2))); $lists = merge($left, $right); return $lists; } function merge(array $left, array $right) { $lists = []; $i = $j = 0; while ($i < count($left) && $j < count($right)) { if ($left[$i] < $right[$j]) { $lists[] = $left[$i]; $i++; } else { $lists[] = $right[$j]; $j++; } } $lists = array_merge($lists, array_slice($left, $i)); $lists = array_merge($lists, array_slice($right, $j)); return $lists; }
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
/** * 基数排序 * * @param array $lists * @return array */ function radix_sort(array $lists) { $radix = 10; $max = max($lists); $k = ceil(log($max, $radix)); if ($max == pow($radix, $k)) { $k++; } for ($i = 1; $i <= $k; $i++) { $newLists = array_fill(0, $radix, []); for ($j = 0; $j < count($lists); $j++) { $key = $lists[$j] / pow($radix, $i - 1) % $radix; $newLists[$key][] = $lists[$j]; } $lists = []; for ($j = 0; $j < $radix; $j++) { $lists = array_merge($lists, $newLists[$j]); } } return $lists; }