|
1
|
|
|
<?php |
|
2
|
|
|
/** |
|
3
|
|
|
* Created by PhpStorm. |
|
4
|
|
|
* User: yiranzai |
|
5
|
|
|
* Date: 19-3-22 |
|
6
|
|
|
* Time: 上午11:21 |
|
7
|
|
|
*/ |
|
8
|
|
|
|
|
9
|
|
|
namespace Yiranzai\Tools; |
|
10
|
|
|
|
|
11
|
|
|
use Exception; |
|
12
|
|
|
|
|
13
|
|
|
class Arr |
|
14
|
|
|
{ |
|
15
|
|
|
/** |
|
16
|
|
|
* 二维数组按照某个字段排序 |
|
17
|
|
|
* @param array $arr 要排序的数组 |
|
18
|
|
|
* @param mixed $field 要排序的字段 |
|
19
|
|
|
* @param int $arg 排序规则 |
|
20
|
|
|
* @return array |
|
21
|
|
|
*/ |
|
22
|
3 |
|
public static function arrSortByField(array $arr, $field, $arg = SORT_ASC): array |
|
23
|
|
|
{ |
|
24
|
3 |
|
if (!empty($arr)) { |
|
25
|
3 |
|
foreach ($arr as $v) { |
|
26
|
3 |
|
$sort[] = $v[$field]; |
|
27
|
|
|
} |
|
28
|
3 |
|
array_multisort($sort, $arg, $arr); |
|
29
|
|
|
} |
|
30
|
3 |
|
return $arr; |
|
31
|
|
|
} |
|
32
|
|
|
|
|
33
|
|
|
/** |
|
34
|
|
|
* 数组group by |
|
35
|
|
|
* @param array $arr |
|
36
|
|
|
* @param string $field |
|
37
|
|
|
* @param bool $unique |
|
38
|
|
|
* @return array |
|
39
|
|
|
* @throws Exception |
|
40
|
|
|
*/ |
|
41
|
3 |
|
public static function arrGroup(array $arr, string $field, $unique = false): array |
|
42
|
|
|
{ |
|
43
|
3 |
|
$group = []; |
|
44
|
3 |
|
foreach ($arr as $item) { |
|
45
|
3 |
|
$groupField = is_array($item) ? Tools::arrGet($item, $field) : Tools::objectGet($item, $field); |
|
46
|
3 |
|
if (empty($groupField) && 0 !== $groupField) { |
|
47
|
|
|
continue; |
|
48
|
|
|
} |
|
49
|
|
|
// 只取其中一个 |
|
50
|
3 |
|
if ($unique) { |
|
51
|
3 |
|
$group[$groupField] = $item; |
|
52
|
|
|
} else { |
|
53
|
3 |
|
$group[$groupField][] = $item; |
|
54
|
|
|
} |
|
55
|
|
|
} |
|
56
|
3 |
|
return $group; |
|
57
|
|
|
} |
|
58
|
|
|
|
|
59
|
|
|
/** |
|
60
|
|
|
* @param array $array |
|
61
|
|
|
* @return array |
|
62
|
|
|
*/ |
|
63
|
3 |
|
public static function heapSort(array $array = []): array |
|
64
|
|
|
{ |
|
65
|
3 |
|
$len = count($array); |
|
66
|
3 |
|
$lastKey = ($len - 1) >> 1; |
|
67
|
|
|
//构建一个大顶堆 |
|
68
|
3 |
|
for ($i = $lastKey; $i >= 0; $i--) { |
|
69
|
3 |
|
self::maxHeapify($array, $i, $len); |
|
70
|
|
|
} |
|
71
|
3 |
|
for ($i = $len - 1; $i > 0; $i--) { |
|
72
|
|
|
//将构建好的大顶堆的顶点与最后一个没排序的点交换 |
|
73
|
3 |
|
self::swap($array[0], $array[$i]); |
|
74
|
|
|
//将剩下的没排序的数据重新构建为一个大顶堆 |
|
75
|
3 |
|
self::maxHeapify($array, 0, $i); |
|
76
|
|
|
} |
|
77
|
3 |
|
return $array; |
|
78
|
|
|
} |
|
79
|
|
|
|
|
80
|
|
|
/** |
|
81
|
|
|
* @param array $arr |
|
82
|
|
|
* @param int $start |
|
83
|
|
|
* @param int $end |
|
84
|
|
|
*/ |
|
85
|
3 |
|
private static function maxHeapify(&$arr, $start, $end): void |
|
86
|
|
|
{ |
|
87
|
3 |
|
$son = $start * 2 + 1; |
|
88
|
3 |
|
if ($son >= $end) { |
|
89
|
3 |
|
return; |
|
90
|
|
|
} |
|
91
|
3 |
|
if ($son + 1 < $end && $arr[$son] < $arr[$son + 1]) { |
|
92
|
3 |
|
$son++; |
|
93
|
|
|
} |
|
94
|
3 |
|
if ($arr[$start] <= $arr[$son]) { |
|
95
|
3 |
|
self::swap($arr[$start], $arr[$son]); |
|
96
|
3 |
|
self::maxHeapify($arr, $son, $end); |
|
97
|
|
|
} |
|
98
|
3 |
|
} |
|
99
|
|
|
|
|
100
|
|
|
/** |
|
101
|
|
|
* @param mixed $a |
|
102
|
|
|
* @param mixed $b |
|
103
|
|
|
*/ |
|
104
|
3 |
|
private static function swap(&$a, &$b): void |
|
105
|
|
|
{ |
|
106
|
3 |
|
$t = $a; |
|
107
|
3 |
|
$a = $b; |
|
108
|
3 |
|
$b = $t; |
|
109
|
3 |
|
} |
|
110
|
|
|
|
|
111
|
|
|
/** |
|
112
|
|
|
* 不断均分为左右两个数组，然后取出两个数组每个相同位置的值，比较大小，并push到队列中，最后按照 队列，左数组，右数组的顺序来合并 |
|
113
|
|
|
* 从最小单元开始排序合并，然后返回到上一个大小的单元进行排序合并 |
|
114
|
|
|
* |
|
115
|
|
|
* @param array $array |
|
116
|
|
|
* @return array |
|
117
|
|
|
*/ |
|
118
|
3 |
|
public static function mergeSort(array $array): array |
|
119
|
|
|
{ |
|
120
|
3 |
|
$len = count($array); |
|
121
|
3 |
|
if ($len <= 1) { |
|
122
|
3 |
|
return $array; |
|
123
|
|
|
} |
|
124
|
|
|
//如果数组长度为奇数，则$m需要等于长度的一半向上补齐整数，偶数则需要等于一半，只有这样array_chunk才能恰好分割为两个长度几乎相同的数组 |
|
125
|
3 |
|
$m = ($len + 1) >> 1; |
|
126
|
3 |
|
[$left, $right] = array_chunk($array, $m); |
|
127
|
3 |
|
$left = self::mergeSort($left); |
|
128
|
3 |
|
$right = self::mergeSort($right); |
|
129
|
3 |
|
$reg = []; |
|
130
|
3 |
|
while (count($left) && count($right)) { |
|
131
|
3 |
|
if ($left[0] < $right[0]) { |
|
132
|
3 |
|
$reg[] = array_shift($left); |
|
133
|
|
|
} else { |
|
134
|
3 |
|
$reg[] = array_shift($right); |
|
135
|
|
|
} |
|
136
|
|
|
} |
|
137
|
3 |
|
return array_merge($reg, $left, $right); |
|
138
|
|
|
} |
|
139
|
|
|
|
|
140
|
|
|
/** |
|
141
|
|
|
* 每次都取中间的那个数，遍历数组，比它大放右边，比它小放左边 |
|
142
|
|
|
* |
|
143
|
|
|
* @param array $array |
|
144
|
|
|
* @return array |
|
145
|
|
|
*/ |
|
146
|
3 |
|
public static function quickSort(array $array): array |
|
147
|
|
|
{ |
|
148
|
3 |
|
$len = count($array); |
|
149
|
3 |
|
if ($len <= 1) { |
|
150
|
3 |
|
return $array; |
|
151
|
|
|
} |
|
152
|
3 |
|
$m = $len >> 1; |
|
153
|
3 |
|
$mValue = $array[$m]; |
|
154
|
3 |
|
$left = $right = []; |
|
155
|
3 |
|
foreach ($array as $key => $iValue) { |
|
156
|
3 |
|
if ($key === $m) { |
|
157
|
3 |
|
continue; |
|
158
|
|
|
} |
|
159
|
3 |
|
if ($iValue < $mValue) { |
|
160
|
3 |
|
$left[] = $iValue; |
|
161
|
|
|
} else { |
|
162
|
3 |
|
$right[] = $iValue; |
|
163
|
|
|
} |
|
164
|
|
|
} |
|
165
|
3 |
|
return array_merge(self::quickSort($left), [$mValue], self::quickSort($right)); |
|
166
|
|
|
} |
|
167
|
|
|
} |
|
168
|
|
|
|
yiranzai /
php-tools
