yulu

php-原地快速排序

发表于

快速排序

首先要理解什么是快速排序:
在平均状况下，排序n个项目要O(n log n)次比较，在最坏情况下需要O(n2)次比较。
说人话,我们可以将快速排序拆解为以下几个步骤：
1.在给定的数列中挑一个元素，称为基数（pivot）;
2.对数列进行排序
若元素大于基数，则将元素排在基数右面；
若元素小于基数，则将元素排在基数左面;
若元素等于基数，将元素放在左右皆可;
这个简单排序结束以后，我们会看到我们找的基数大体应该在数列的中间位置，这个称为叫做分区;
3.对基数两边的数列进行递归操作。

其实，说的简单点就是以数列中的一个数为基准不断的对数列进行分区，等数列中元素的个数为1时即达到排序结果。
下面是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
<?php
/**
*   Copyright (C) pianke 2017 All rights reserved.
*
*   FileName      ：quick.php
*   Date          ：2017/04/06 10:04:22
*   Version       ：1.0
 */
function swap(&$arr,$ori,$target)
{
	$tmp = $arr[$ori];
	$arr[$ori] = $arr[$target];
	$arr[$target] = $tmp;
}
function quick(&$arr,$start,$end)
{
	if(!is_array($arr)){
		return false;
	}
	$pviot = $arr[$end];
	$index = $start - 1;
	for ($current = $start; $current < $end; $current++)
	{
		if($arr[$current] <= $pviot){
			#index++
			$index++;
			#swap(index,current)
			swap($arr,$index,$current);
		}
	}
	$index = $index + 1;
	swap($arr,$index,$end);
	return $index;
	//print_r($arr);
}
function sort_test(&$arr,$start,$end)
{
	if($start < $end){
		$index = quick($arr,$start,$end);
		sort_test($arr,$start,$index-1);
		sort_test($arr,$index+1,$end);
	}
}
//$list = [2,8,7,1,3,5,6,4];
$list = [5,2,3,9,1,7,6,4,8];
$count = count($list);
sort_test($list,0,$count-1);
print_r($list);

附一个代码的图解