/
QuickSort.php
91 lines (73 loc) · 2.12 KB
/
QuickSort.php
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
<?php
/**
*
* 快速排序:
* 关注枢纽元的选取,简单的方式是取第一个,其次是随机选择,最优是使用三数中值法
*
* 1. 如果序列长度为1,直接返回序列
* 2. 使用三数中值法获取中间元素[比较序列的开头,结尾和中间元素,取三个值中的中间值]
* 3. 将小于中间元素的数放到左序列,将大于中间元素的数放到右序列
* 4. 对左序列和右序列递归应用1,2,3步骤
*
*/
class QuickSort
{
private $originalData = [];
private $resultData = [];
public function __construct($original = [])
{
$this->originalData = $original;
}
public function sort()
{
$this->resultData = $this->quick($this->originalData);
return $this->resultData;
}
protected function quick($originalData)
{
$lenght = count($originalData);
if ($lenght <= 1) {
return $originalData;
}
$pivot = $this->threeMiddleValue($originalData, 0, $lenght - 1);
$leftData = [];
$rightData = [];
for($i = 0; $i < $lenght; $i++) {
if ($originalData[$i] < $pivot) {
$leftData[] = $originalData[$i];
} else if ($originalData[$i] > $pivot){
$rightData[] = $originalData[$i];
}
}
$leftData = $this->quick($leftData);
$rightData = $this->quick($rightData);
return array_merge($leftData, [$pivot], $rightData);
}
public function threeMiddleValue($arr, $left, $right)
{
$result = null;
$middle = floor(($left + $right)/2);
if ($arr[$left] > $arr[$right]) {
if ($arr[$left] < $arr[$middle]) {
$result = $arr[$left];
} else if ($arr[$right] > $arr[$middle]) {
$result = $arr[$right];
} else {
$result = $arr[$middle];
}
} else {
if ($arr[$right] < $arr[$middle]) {
$result = $arr[$right];
} else if ($arr[$left] > $arr[$middle]) {
$result = $arr[$left];
} else {
$result = $arr[$middle];
}
}
return $result;
}
}
$testData = [7, 3, 10, 5, 1, 8];
$quickSort = new QuickSort($testData);
echo '<pre>';
var_dump($quickSort->sort());