面试最常遇到的4种常用排序算法（实例用php实现）

<?php
/*
* 升序排列
*/
class Sort
{
 /*
 * 冒泡排序, 稳定，时间复杂度O(n^2)
 */
 public static function bubbleSort($src_arr)
 {
 $n = count($src_arr);
 for($i=0;$i<$n-1;$i++)
 {
 for($j=0;$j<$n-$i-1;$j++)
 {
 if ($src_arr[$j] < $src_arr[$j+1])
 {
 $tmp = $src_arr[$j];
 $src_arr[$j] = $src_arr[$j+1];
 $src_arr[$j+1] = $tmp;
 }
 }
 }
 return $src_arr;
 }
 /*
 * 优化冒泡排序, 不稳定，最好时间O(n)
 * 如果没到最后一轮比较已经排好，则终止排序
 */
 public static function bubbleSortBetter($src_arr)
 {
 $n = count($src_arr);
 $flag = false;
 for($i=0;$i<$n-1;$i++)
 {
 for($j=0;$j<$n-$i-1;$j++)
 {
 if ($src_arr[$j] < $src_arr[$j+1])
 {
 $tmp = $src_arr[$j];
 $src_arr[$j] = $src_arr[$j+1];
 $src_arr[$j+1] = $tmp;
 $flag = true;
 }
 }
 if (!$flag) break;
 }
 return $src_arr;
 }
 /*
 * 选择排序, 不稳定，时间复杂度O(n^2)
 */
 public static function selectSort($src_arr)
 {
 for($i=0;$i<count($src_arr)-1;$i++)
 {
 for($j=$i+1;$j<count($src_arr);$j++)
 {
 if ($src_arr[$j] < $src_arr[$i])
 {
 $tmp = $src_arr[$j];
 $src_arr[$j] = $src_arr[$i];
 $src_arr[$i] = $tmp;
 }
 }
 }
 return $src_arr;
 }
 /*
 * 插入排序, 稳定，时间复杂度O(n^2)
 */
 public static function insertSort($src_arr)
 {
 for($i=1;$i<count($src_arr);$i++)
 {
 $insertVal = $src_arr[$i];
 $insertIndex = $i - 1;
 while($insertIndex >= 0 && $insertVal < $src_arr[$insertIndex])
 {
 $src_arr[$insertIndex + 1] = $src_arr[$insertIndex];
 $insertIndex--;
 }
 $src_ar[$insertIndex] = $insertVal;
 }
 return $src_arr;
 }
 /*
 * 快速排序, 不稳定，时间复杂度：O(nlongn) ~ O(n^2)
 */
 public static function quickSort($src_arr)
 {
 if (count($src_arr) < 1)
 {
 return $src_arr;
 }
 $key = $src_arr[0];
 $left_arr = array();
 $right_arr = array();
 for($i=1;$i<count($src_arr);$i++)
 {
 if ($src_arr[$i] <= $key)
 {
 $left_arr[] = $src_arr[$i];
 }
 else
 {
 $right_arr[] = $src_arr[$i];
 }
 $left_arr = self::quickSort($left_arr);
 $right_arr = self::quickSort($right_arr);
 return array_merge($left_arr, $right_arr);
 }
 }
}
$source = array('5', '9', '13', '20', '36', '38', '48', '51', '59', '63', '65', '71', '73', '75', '76', '85', '89', '93', '100', '106', '108', '108', '109', '109', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6');
$time1 = microtime();
$sort = Sort::bubbleSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '冒泡共使用时间:'.$timeuse."\n";
$time1 = microtime();
$sort = Sort::bubbleSortBetter($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '优化冒泡共使用时间:'.$timeuse."\n";
$time1 = microtime();
$sort = Sort::selectSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '选择排序共使用时间:'.$timeuse."\n";
$time1 = microtime();
$sort = Sort::insertSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '插入排序共使用时间:'.$timeuse."\n";
$time1 = microtime();
$sort = Sort::quickSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '快速排序共使用时间:'.$timeuse."\n";
?>