选择排序分为简单选择排序、树形选择排序和堆排序三类，此三类中，简单选择排序是最简单，也是最好理解的。
概念
选择排序 - Selection Sort：是一种简单直观的排序算法。顾名思意，就是直接从待排序数组里选择一个最小(或最大)的数字，每次都拿一个最小数字出来，顺序放入新数组，直到全部拿完
步骤
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 以此类推，直到所有元素均排序完毕
实现
方式一
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
| <?php
class SelectionSort
{
/**
* 主运行方法
*
* @return void
*/
public static function main(): void
{
$random = self::random();
$array = self::sort($random);
print_r($array);
}
/**
* 选择排序
*
* @param array $array
*
* @return array
*/
public static function sort(array &$array): array
{
$count = count($array);
for ($i = 0; $i < $count; $i++) {
$position = $i;
for ($j = $i + 1; $j < $count; $j++) {
if (self::compare($array[$position], $array[$j]) > 0) {
$position = $j;
}
}
if ($position !== $i) {
self::swap($array[$position], $array[$i]);
}
}
return $array;
}
/**
* 比较大小
*
* @param int $x
* @param int $y
*
* @return int
*/
private static function compare(int $x, int $y): int
{
return $x <=> $y;
}
/**
* 互换位置
*
* @param int $x
* @param int $y
*
* @return void
*/
private static function swap(int &$x, int &$y): void
{
if ($x !== $y) {
$t = $x;
$x = $y;
$y = $t;
}
}
/**
* 生成随机数组
*
* @param int $low
* @param int $high
* @param int $num
*
* @return array
*/
private static function random(int $low = 1, int $high = 9999, int $num = 10): array
{
$num = $num > $high ? $high : $num;
$range = range($low, $high);
$array = array_rand(array_flip($range), $num);
shuffle($array);
return $array;
}
}
SelectionSort::main();
// 结果
Array
(
[0] => 312
[1] => 1124
[2] => 1267
[3] => 1884
[4] => 2609
[5] => 4177
[6] => 4773
[7] => 7728
[8] => 8237
[9] => 8963
)
|
方式二
树形选择排序 - Tree Selection Sort：又名锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法
1
2
3
| <?php
// 这个算法目前搞不定，预留位置，待以后再实现
|
方式三
堆排序 - Heap Sort：是指利用堆这种数据结构所设计的一种排序算法。它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶
1
2
3
| <?php
// 这个算法目前搞不定，预留位置，待以后再实现
|