scripts/quickSort.php at master · jwcn/scripts · GitHub

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
<?php
// 快速排序

function quickSort(array $arr) {
	if (count($arr) < 2) return $arr;

	$left = 0;
	$right = count($arr) - 1;

	foreach ($arr as $key => $value) {
		if ($value < $arr[$right]) {
			$arr[$key] = $arr[$left];
			$arr[$left] = $value;
			$left++;
		}
	}

	$tmp = $arr[$right];
	$arr[$right] = $arr[$left];
	$arr[$left] = $tmp;

	// $l = quickSort(array_slice($arr, 0, $left));
	// $r = quickSort(array_slice($arr, $left));
	// return array_merge($l, $r);

	// quick
	$l = quickSort(array_slice($arr, 0, $left));
	$r = quickSort(array_slice($arr, $left+1));
	return array_merge($l, $value, $r);
}

$res = quickSort([3,7,2,4,5]);
print_r($res);


function quickSort2($arr) {
	if(count($arr) < 2)
		return $arr;

	$base = $arr[0];
	$left = $right = [];

	foreach ($arr as $key => $value) {
		if ($value < $base) {
			$left[] = $value;
		}else {
			$right[] = $value;
		}
	}

	array_shift($right);


	$left = quickSort2($left);
	$right = quickSort2($right);

	return array_merge($left, [$base], $right);
}