Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 668ed83

Browse files
wilonidsbllp
authored andcommitted
添加PHP代码实现及测试文件 (hustcc#18)
1 parent 682115d commit 668ed83

11 files changed

+609
-0
lines changed

‎1.bubbleSort.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -110,3 +110,22 @@ public class BubbleSort implements IArraySort {
110110
}
111111
}
112112
```
113+
114+
## 9. PHP 代码实现
115+
116+
```php
117+
function bubbleSort($arr)
118+
{
119+
$len = count($arr);
120+
for ($i = 0; $i < $len - 1; $i++) {
121+
for ($j = 0; $j < $len - 1 - $i; $j++) {
122+
if ($arr[$j] > $arr[$j+1]) {
123+
$tmp = $arr[$j];
124+
$arr[$j] = $arr[$j+1];
125+
$arr[$j+1] = $tmp;
126+
}
127+
}
128+
}
129+
return $arr;
130+
}
131+
```

‎10.radixSort.md

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -133,3 +133,40 @@ public class RadixSort implements IArraySort {
133133
}
134134
}
135135
```
136+
137+
## 5. PHP 代码实现
138+
139+
```php
140+
function radixSort($arr, $maxDigit = null)
141+
{
142+
if ($maxDigit === null) {
143+
$maxDigit = max($arr);
144+
}
145+
$counter = [];
146+
for ($i = 0; $i < $maxDigit; $i++) {
147+
for ($j = 0; $j < count($arr); $j++) {
148+
preg_match_all('/\d/', (string) $arr[$j], $matches);
149+
$numArr = $matches[0];
150+
$lenTmp = count($numArr);
151+
$bucket = array_key_exists($lenTmp - $i - 1, $numArr)
152+
? intval($numArr[$lenTmp - $i - 1])
153+
: 0;
154+
if (!array_key_exists($bucket, $counter)) {
155+
$counter[$bucket] = [];
156+
}
157+
$counter[$bucket][] = $arr[$j];
158+
}
159+
$pos = 0;
160+
for ($j = 0; $j < count($counter); $j++) {
161+
$value = null;
162+
if ($counter[$j] !== null) {
163+
while (($value = array_shift($counter[$j])) !== null) {
164+
$arr[$pos++] = $value;
165+
}
166+
}
167+
}
168+
}
169+
170+
return $arr;
171+
}
172+
```

‎2.selectionSort.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,3 +105,24 @@ public class SelectionSort implements IArraySort {
105105
}
106106
}
107107
```
108+
109+
## 7. PHP 代码实现
110+
111+
```php
112+
function selectionSort($arr)
113+
{
114+
$len = count($arr);
115+
for ($i = 0; $i < $len - 1; $i++) {
116+
$minIndex = $i;
117+
for ($j = $i + 1; $j < $len; $j++) {
118+
if ($arr[$j] < $arr[$minIndex]) {
119+
$minIndex = $j;
120+
}
121+
}
122+
$temp = $arr[$i];
123+
$arr[$i] = $arr[$minIndex];
124+
$arr[$minIndex] = $temp;
125+
}
126+
return $arr;
127+
}
128+
```

‎3.insertionSort.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -99,3 +99,22 @@ public class InsertSort implements IArraySort {
9999
}
100100
}
101101
```
102+
103+
## 7. PHP 代码实现
104+
105+
```php
106+
function insertionSort($arr)
107+
{
108+
$len = count($arr);
109+
for ($i = 1; $i < $len; $i++) {
110+
$preIndex = $i - 1;
111+
$current = $arr[$i];
112+
while($preIndex >= 0 && $arr[$preIndex] > $current) {
113+
$arr[$preIndex+1] = $arr[$preIndex];
114+
$preIndex--;
115+
}
116+
$arr[$preIndex+1] = $current;
117+
}
118+
return $arr;
119+
}
120+
```

‎4.shellSort.md

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,3 +120,27 @@ public class ShellSort implements IArraySort {
120120
}
121121
}
122122
```
123+
124+
## 6. PHP 代码实现
125+
126+
```php
127+
function shellSort($arr)
128+
{
129+
$len = count($arr);
130+
$temp = 0;
131+
$gap = 1;
132+
while($gap < $len / 3) {
133+
$gap = $gap * 3 + 1;
134+
}
135+
for ($gap; $gap > 0; $gap = floor($gap / 3)) {
136+
for ($i = $gap; $i < $len; $i++) {
137+
$temp = $arr[$i];
138+
for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
139+
$arr[$j+$gap] = $arr[$j];
140+
}
141+
$arr[$j+$gap] = $temp;
142+
}
143+
}
144+
return $arr;
145+
}
146+
```

‎5.mergeSort.md

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,3 +186,40 @@ public class MergeSort implements IArraySort {
186186

187187
}
188188
```
189+
190+
## 8. PHP 代码实现
191+
192+
```php
193+
function mergeSort($arr)
194+
{
195+
$len = count($arr);
196+
if ($len < 2) {
197+
return $arr;
198+
}
199+
$middle = floor($len / 2);
200+
$left = array_slice($arr, 0, $middle);
201+
$right = array_slice($arr, $middle);
202+
return merge(mergeSort($left), mergeSort($right));
203+
}
204+
205+
function merge($left, $right)
206+
{
207+
$result = [];
208+
209+
while (count($left) > 0 && count($right) > 0) {
210+
if ($left[0] <= $right[0]) {
211+
$result[] = array_shift($left);
212+
} else {
213+
$result[] = array_shift($right);
214+
}
215+
}
216+
217+
while (count($left))
218+
$result[] = array_shift($left);
219+
220+
while (count($right))
221+
$result[] = array_shift($right);
222+
223+
return $result;
224+
}
225+
```

‎6.quickSort.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -228,3 +228,28 @@ public class QuickSort implements IArraySort {
228228
229229
}
230230
```
231+
232+
## 8. PHP 代码实现
233+
234+
```php
235+
function quickSort($arr)
236+
{
237+
if (count($arr) <= 1)
238+
return $arr;
239+
$middle = $arr[0];
240+
$leftArray = array();
241+
$rightArray = array();
242+
243+
for ($i = 1; $i < count($arr); $i++) {
244+
if ($arr[$i] > $middle)
245+
$rightArray[] = $arr[$i];
246+
else
247+
$leftArray[] = $arr[$i];
248+
}
249+
$leftArray = quickSort($leftArray);
250+
$leftArray[] = $middle;
251+
252+
$rightArray = quickSort($rightArray);
253+
return array_merge($leftArray, $rightArray);
254+
}
255+
```

‎7.heapSort.md

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -203,3 +203,55 @@ public class HeapSort implements IArraySort {
203203

204204
}
205205
```
206+
207+
## 7. PHP 代码实现
208+
209+
```php
210+
function buildMaxHeap(&$arr)
211+
{
212+
global $len;
213+
for ($i = floor($len/2); $i >= 0; $i--) {
214+
heapify($arr, $i);
215+
}
216+
}
217+
218+
function heapify(&$arr, $i)
219+
{
220+
global $len;
221+
$left = 2 * $i + 1;
222+
$right = 2 * $i + 2;
223+
$largest = $i;
224+
225+
if ($left < $len && $arr[$left] > $arr[$largest]) {
226+
$largest = $left;
227+
}
228+
229+
if ($right < $len && $arr[$right] > $arr[$largest]) {
230+
$largest = $right;
231+
}
232+
233+
if ($largest != $i) {
234+
swap($arr, $i, $largest);
235+
heapify($arr, $largest);
236+
}
237+
}
238+
239+
function swap(&$arr, $i, $j)
240+
{
241+
$temp = $arr[$i];
242+
$arr[$i] = $arr[$j];
243+
$arr[$j] = $temp;
244+
}
245+
246+
function heapSort($arr) {
247+
global $len;
248+
$len = count($arr);
249+
buildMaxHeap($arr);
250+
for ($i = count($arr) - 1; $i > 0; $i--) {
251+
swap($arr, 0, $i);
252+
$len--;
253+
heapify($arr, 0);
254+
}
255+
return $arr;
256+
}
257+
```

‎8.countingSort.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,3 +126,32 @@ public class CountingSort implements IArraySort {
126126

127127
}
128128
```
129+
130+
## 6. PHP 代码实现
131+
132+
```php
133+
function countingSort($arr, $maxValue = null)
134+
{
135+
if ($maxValue === null) {
136+
$maxValue = max($arr);
137+
}
138+
for ($m = 0; $m < $maxValue + 1; $m++) {
139+
$bucket[] = null;
140+
}
141+
142+
$arrLen = count($arr);
143+
for ($i = 0; $i < $arrLen; $i++) {
144+
if (!array_key_exists($arr[$i], $bucket)) {
145+
$bucket[$arr[$i]] = 0;
146+
}
147+
$bucket[$arr[$i]]++;
148+
}
149+
150+
$sortedIndex = 0;
151+
foreach ($bucket as $key => $len) {
152+
if ($len !== null) $arr[$sortedIndex++] = $key;
153+
}
154+
155+
return $arr;
156+
}
157+
```

‎9.bucketSort.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -131,3 +131,45 @@ public class BucketSort implements IArraySort {
131131

132132
}
133133
```
134+
135+
## 5. PHP 代码实现
136+
137+
```php
138+
function bucketSort($arr, $bucketSize = 5)
139+
{
140+
if (count($arr) === 0) {
141+
return $arr;
142+
}
143+
144+
$minValue = $arr[0];
145+
$maxValue = $arr[0];
146+
for ($i = 1; $i < count($arr); $i++) {
147+
if ($arr[$i] < $minValue) {
148+
$minValue = $arr[$i];
149+
} else if ($arr[$i] > $maxValue) {
150+
$maxValue = $arr[$i];
151+
}
152+
}
153+
154+
$bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
155+
$buckets = array();
156+
for ($i = 0; $i < count($buckets); $i++) {
157+
$buckets[$i] = [];
158+
}
159+
160+
for ($i = 0; $i < count($arr); $i++) {
161+
$buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
162+
}
163+
164+
$arr = array();
165+
for ($i = 0; $i < count($buckets); $i++) {
166+
$bucketTmp = $buckets[$i];
167+
sort($bucketTmp);
168+
for ($j = 0; $j < count($bucketTmp); $j++) {
169+
$arr[] = $bucketTmp[$j];
170+
}
171+
}
172+
173+
return $arr;
174+
}
175+
```

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /