PHP版算法--快速排序的实现

快速排序原理

快速排序使用分治法实现，其思想是寻找基准点然后进行比较，小于基准点的数放到其左边，大于的数放到其右边。

正常的情况下，时间复杂度是O(nlogn)；最坏的情况其时间复杂度是 O(n2)。

分治法实现快速排序的步骤

• 1、从数列中挑出一个数作为基准元素，通常选择第一个或最后一个元素，也有选择中间的；
• 2、扫描数列，把基准元素作为比较对象，将数列分成两个数组，小于基准元素的数在其左边，大于基准元素的数在其右边；
• 3、使用同样的方式继续排序，完成后，基准元素位置在两个排序位置的中间。

手动解析理解

// 待排序数组
$arr = [5,192,9,10,291,49,1,4,149,65,11,12];

1)选第一个元素 5 作为基准元素；
2)基准元素5和数组中和所有元素进行比较，小于5的放在左边，大于5的放在右边，得到如下数据;
[1,4] [192,9,10,291,49,149,65,11,12]
3)采用递归，再次比较

代码实现

1、结合递归实现快速排序

/**
 * quick_sort 快速排序
 * 
 * @param array $arr 	待排序的数组
 *
 * @return array
 **/
function quick_sort(array $arr) {
	// 统计数组长度
	$arrayLength = count($arr);

	// 排除不符合要求的数组
	if ($arrayLength <= 1) {
		return $arr;
	}

	// 取数组第一个元素基准元素，用于比较
	$pivot    = $arr[0];
	// 小于基准元素的数组放在左边
	$leftArr  = [];
	// 大于基准元素的数组放在右边
	$rightArr = [];


	/**
	 * 遍历数组
	 * 
	 * 注意，此处索引 $i是从1开始的，
	 * 原因是我们将第一个数组元素值拿了出来作为基准元素，
	 * 因此，索引从1开始
	 **/
	for ($i = 1; $i < $arrayLength; $i++) {
		// 扫描比较基准元素
		if ($arr[$i] > $pivot) {
			// 大于基准元素的值放到右边
			$rightArr[] = $arr[$i];
		} else {
			// 小于基准元素的值放到左边
			$leftArr[] = $arr[$i];
		}
	}

	// 递归调用
	$leftArr = quick_sort($leftArr);
	$rightArr = quick_sort($rightArr);

	// 合并数组，基准元素需要转为数组，并放在这两个数组中间
	return array_merge($leftArr, array($pivot), $rightArr);
}

$arr = [5,192,9,10,291,49,1,4,149,65,11,12];

// 计算程序运行的时间（微秒）
$startTime = microtime(true);
print_r(quick_sort($arr));
$endTime = microtime(true);

echo $endTime - $startTime;

打印结果如下

// 排序结果
Array ( [0] => 1 [1] => 4 [2] => 5 [3] => 9 [4] => 10 [5] => 11 [6] => 12 [7] => 49 [8] => 65 [9] => 149 [10] => 192 [11] => 291 ) 
// 算法所花费的时间（微秒）
1.1920928955078E-5

我是温新，每天进步一点点，就一点点。