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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| /**
* 二分查找(数组里查找某个元素)
* @param array $array
* @param int $low 最小索引
* @param int $high 最大索引
* @param mixed $search 待查找元素
* @return mixed
*/
function binSch($array, $low, $high, $search)
{
if ($low <= $high) {
$mid = intval(($low + $high) / 2);
if ($array[$mid] == $search) {
return $mid;
} elseif ($search < $array[$mid]) {
return binSch($array, $low, $mid - 1, $search);
} else {
return binSch($array, $mid + 1, $high, $search);
}
}
return -1;
}
// $arr = [1,3,4,5,6,7];
// $res = binSch($arr,0,5,3);
// var_export($res);
/**
* 顺序查找(数组里查找某个元素)
* @param array $array
* @param int $n 数组长度
* @param mixed $k 待查元素
* @return mixed
*/
function seqSch(array $array, int $n, $k)
{
$array[$n] = $k;
for ($i = 0; $i < $n; $i++) {
if ($array[$i] == $k) {
break;
}
}
if ($i < $n) {
return $i;
} else {
return -1;
}
}
// $arr = [1, 3, 4, 5, 6, 7];
// $res = seqSch($arr, 6, 7);
// var_export($res);
/**
* 线性表的删除(数组删除)
* @param array $array
* @param int $i 待删除索引
* @return mixed
*/
function delete_array_element(array $array, $i)
{
// var_export($array);
$len = count($array);
for ($j = $i; $j < $len - 1; $j++) {
$array[$j] = $array[$j + 1];
}
array_pop($array);
return $array;
}
// $arr = [1, 3, 4, 5, 6, 7];
// $res = delete_array_element($arr, 5);
// var_export($res);
/**
* 冒泡排序(找出最小,向左)
* @param array $array
* @return array
*/
function bubble_sort1($array)
{
$count = count($array);
if ($count <= 0) {
return [];
}
for ($i = 0; $i < $count; $i++) {
for ($j = $count - 1; $j > $i; $j--) {
if ($array[$j] < $array[$j - 1]) {
$tmp = $array[$j];
$array[$j] = $array[$j - 1];
$array[$j - 1] = $tmp;
}
}
}
return $array;
}
// $arr = [1, 3, 4, 5, 6, 7];
// shuffle($arr);
// $res = bubble_sort1($arr);
// var_export($res);
/**
* 冒泡排序(找出最大,向右)
* @param array $array
* @return array
*/
function bubble_sort($arr)
{
$count = count($arr);
if ($count <= 0) {
return [];
}
for ($i = 0; $i < $count - 1; $i++) {
for ($j = 0; $j < $count - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $tmp;
}
}
}
return $arr;
}
// $arr = [1, 3, 4, 5, 6, 7];
// shuffle($arr);
// $res = bubble_sort($arr);
// var_export($res);
/**
* 快速排序(数组排序)
* @param array $array 待排数组
* @return array
*/
function quick_sort($array)
{
if (count($array) <= 1) {
return $array;
}
$key = $array[0];
$left_arr = array();
$right_arr = array();
for ($i = 1; $i < count($array); $i++) {
if ($array[$i] <= $key) {
$left_arr[] = $array[$i];
} else {
$right_arr[] = $array[$i];
}
}
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
return array_merge($left_arr, [$key], $right_arr);
}
// $arr = [5, 7, 6, 4, 3, 1, 8];
// $res = quick_sort($arr);
// var_export($res);
|
