常见排序算法

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
<?php
/**
* 排序算法php实现
*/
run();

function run()
{
$array = [31, 54, 6, 15, 76, 8, 35, 3, 100, 31, 45];
//01 冒泡排序
$bubbleSortArray = bubbleSort($array);

//02 插入排序
$insertSortArray = insertSort($array);

//03 选择排序
$selectSortArray = selectSort($array);

//04 希尔排序
$shellSortArray = shellSort($array);

//05 堆排序
$heapSortArray = heapSort($array);

//06 归并排序
$mergeSortArray = mergeSort($array);

//07 快速排序
$quickSortArray = quickSort($array);

echo PHP_EOL."冒泡排序:";
var_export($bubbleSortArray);
echo PHP_EOL."插入排序:";
var_export($insertSortArray);
echo PHP_EOL."选择排序:";
var_export($selectSortArray);
echo PHP_EOL."希尔排序:";
var_export($shellSortArray);
echo PHP_EOL."堆排序:";
var_export($heapSortArray);
echo PHP_EOL."归并排序:";
var_export($mergeSortArray);
echo PHP_EOL."快速排序:";
var_export($quickSortArray);
return;
}

function bubbleSort($array)
{
/**
* 01 冒泡排序
* 说明:就是第一个位置上的数与他相邻第二个位置上的数比较,
* 如果比他相邻的数小,则两者交换位置,否则不交换。
* 接着第一个位置上的数与第三个位置上的数比较大小,也是小则交换,
* 一直到和最后一个位置的数比较交换完毕。
* 然后,是下一个循环,就是第二个位置上的数重复上面的比较交换操作,
* 直到把整个数列变成是一个从小到大的有序序列。
*/
$count = count($array);
for ($i = 0; $i < $count; $i++) {
for ($j=$i+1; $j<$count; $j++) {
if ($array[$i] > $array[$j]) {
list($array[$i], $array[$j]) = [$array[$j],$array[$i]];
}
}
}
return $array;
}

function insertSort($array)
{
/**
* 02 插入排序
* 说明:从一堆待排序的数列中选出来一个最小值(可以认为第一个数就是已排序的数列),
* 然后从剩余的带排序的数列中选出来最小值有序放到已排序的数列中,
* 依次操作,直到最后的数列都是一个从小到大的有序数列为止
*/
$count = count($array);
for ($i = 1; $i < $count; $i++) {
$min = $i;
//拿出待排序中的最小值
for ($j = $i + 1; $j < $count; $j++) {
if ($array[$min] > $array[$j]) {
$min = $j;
}
}
//交换,而不是直接赋值,否则会有数据丢失
swap($array[$i], $array[$min]);

//拿出的值插入到已排序的数列中
for ($k=$i-1; $k>=0; $k--) {
if ($array[$i] < $array[$k]) {
swap($array[$i], $array[$k]);
}
break;
}
}
return $array;
}


function selectSort($array)
{
/**
* 03 选择排序
* 说明:从一堆待排序的数列中选出来一个最小值,放到新的数组的第一个位置,
* 继续从剩余的数列中选取最小值放入到数组中,重复上面的步骤,将数字都取出来排成新的有序数列
*/
$count = count($array);
$newArr = array();
for ($i=0; $i< $count; $i++) {
$min = selectSortChild($array);
// var_dump($min);
$newArr[$i] = $array[$min];
unset($array[$min]);

//unset底层源码只是将min元素指针指向了null,所以需要下面的操作,否则排序结果后几项都是NULL
$array = array_merge($array, []);
}
return $newArr;
}

//选择排序子函数
function selectSortChild($array)
{
$count = count($array);
$min = 0;
//拿出带排序中的最小值
for($j = 1; $j < $count; $j++) {
if($array[$min] > $array[$j]) {
$min = $j;
}
}
return $min;
}

//04 希尔排序
function shellSort($array)
{
/**
* 04 希尔排序
* 说明:插入排序的一种改进,
* 先比较一定距离的元素成为有序数列,再比较缩小增量距离的元素(可为元素的数量的一半),
* 一直到比较的是相邻元素的时候,就成为了插入排序。
*/
//三层循
$count = count($array);
for ($loop = floor($count); $loop > 0; $loop = floor($loop/2)) {
for ($i=$loop; $i<$count; $i++) {
for ($j=$i-$loop; $j>=0 && $array[$j] > $array[$j+$loop]; $j = $j-$loop) {
swap($array[$j], $array[$j+$loop]);
}
}
}
return $array;

}

//05 堆排序
function heapSort($array)
{
/**
* 05 堆排序 说明:
* 1) 构造大顶堆
* 2)交换堆顶和堆底
* 3)重复前面的步骤升序排列完成
*/
$count = count($array);
//1. 构造大顶堆
for ($i=floor($count/2) - 1; $i>=0; $i--) {
adjustHeap($array, $i, $count);
}

//2. 排序
for ($j=$count-1; $j>=0; $j--) {
swap($array[0], $array[$j]);
adjustHeap($array, 0, $j);
}

return $array;

}

//堆排序子函数
function adjustHeap(&$array, $i, $length)
{
if($i<0)
return false;
$tmp = $array[$i];
for ($j=$i*2+1; $j<$length; $j=$j*2+1) {
if ($j+1< $length && $array[$j] < $array[$j+1])//右子节点比左子节点大,则j指向右子节点
$j++;

if ($array[$j] > $tmp) { //子节点比父节点大,则将子节点的值赋给父节点(不用交换)
$array[$i] = $array[$j];
$i = $j;
} else {
break;
}

}
$array[$i] = $tmp;//实现交换(i有变化时)

}

//06 归并排序
function mergeSort($array)
{
/**
* 06 归并排序
* 说明:将待排序的数列看成是单个的有序的数列,
* 然后进行合并,直到合并成最后的完整有序的数列
*/
//1.进行归并
$length = count($array);
for ($gap = 1; $gap<$length; $gap = $gap*2) {
mergePass($array, $gap, $length);
}
return $array;
}

//归并排序子函数1--合并
function mergePass (&$array, $gap, $length)
{
//1. 归并长度是gap的相邻两个子表
for ($i=0; $i+2*$gap-1<$length; $i=$i+2*$gap) {
merge($array, $i, $i+$gap-1, $i+2*$gap-1);
}

//2. 余下的两个字表合并,后者的长度小于gap
if ($i+$gap-1 < $length) {
merge($array, $i, $i+$gap-1, $length-1);
}
}

//归并排序子函数2--合并两个有序序列
function merge(&$array, $low, $mid, $high)
{
$i = $low;//第一段序列的下标
$j = $mid + 1;//第二段序列的下标
$k = 0;
$arrayNew = array();//新的临时合并数组

//扫描第一段序列和第二段序列,直到有一个序列扫描完毕
while ($i<=$mid && $j<=$high) {
//比较两个合并的数组,小的放到新的临时合并数组中
if ($array[$i] > $array[$j]) {
$arrayNew[$k] = $array[$j];
$k++;
$j++;
} else {
$arrayNew[$k] = $array[$i];
$k++;
$i++;
}
}

//数组1中有没扫描的元素,直接复制到新数组中
while ($i <= $mid) {
$arrayNew[$k] = $array[$i];
$k++;
$i++;
}

//数组2中有没扫描的元素,直接复制到新数组中
while ($j <= $high) {
$arrayNew[$k] = $array[$j];
$k++;
$j++;
}

//将合并新数组复制到原数组中
for ($i=$low,$k=0; $i<=$high; $i++,$k++) {
$array[$i] = $arrayNew[$k];
}
}

//交换数据
function swap (&$a, &$b)
{
$res = $a;
$a = $b;
$b = $res;
}

function quickSort($array)
{
// 判断是否需要运行,因下面已拿出一个中间值,这里<=1
if (count($array) <= 1) {
return $array;
}

$middle = $array[0]; // 中间值

$left = []; // 接收小于中间值
$right = [];// 接收大于中间值
$equal = [];
$equal[] = $middle;

// 循环比较
for ($i=1; $i < count($array); $i++) {
if ($middle == $array[$i]) {
$equal[] = $array[$i];
} elseif ($middle < $array[$i]) {
$right[] = $array[$i];
} else {
$left[] = $array[$i];
}
}

// 递归排序划分好的2边
$left = quickSort($left);
$right = quickSort($right);

// 合并排序后的数据,别忘了合并中间值
return array_merge($left, $equal, $right);
}