插入排序是一种较为简单的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。为此有人形象的把插入排序比拟为打扑克抓牌的过程，通常我们右手抓牌，没抓一张牌，就放到左手，抓下一张牌后，会把这张牌依次与左手上的牌比较，并把它插入到一个合适的位置（按牌面大小），这个比拟实在是太牛逼了。
概念
插入排序 - Insertion Sort：是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤 2~5
实现
方案一
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
| <?php
class InsertionSort
{
/**
* 主运行方法
*
* @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) - 1;
for ($i = 0; $i < $count; $i++) {
for ($j = $i; $j >= 0; $j--) {
if (self::compare($array[$j], $array[$j + 1]) > 0) {
self::swap($array[$j], $array[$j + 1]);
} else {
break;
}
}
}
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;
}
}
InsertionSort::main();
// 结果
Array
(
[0] => 84
[1] => 1841
[2] => 3900
[3] => 4762
[4] => 5708
[5] => 5938
[6] => 6136
[7] => 6148
[8] => 6228
[9] => 9207
)
|
方案二
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
| <?php
class InsertionSort
{
/**
* 主运行方法
*
* @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) - 1;
for ($i = 0; $i < $count; $i++) {
if (self::compare($array[$i], $array[$i + 1]) > 0) {
$pivot = $array[$i + 1];
for ($j = $i; $j >= 0 && $array[$j] > $pivot; $j--) {
$array[$j + 1] = $array[$j];
}
$array[$j + 1] = $pivot;
}
}
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;
}
}
InsertionSort::main();
// 结果
Array
(
[0] => 133
[1] => 161
[2] => 393
[3] => 1273
[4] => 1274
[5] => 2041
[6] => 5046
[7] => 7325
[8] => 7950
[9] => 9988
)
|
方案三
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
| <?php
class InsertionSort
{
/**
* 主运行方法
*
* @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) - 1;
for ($i = 0; $i < $count; $i++) {
for ($j = $i; $j >= 0 && self::compare($array[$j], $array[$j + 1]) > 0; $j--) {
self::swap($array[$j], $array[$j + 1]);
}
}
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;
}
}
InsertionSort::main();
// 结果
Array
(
[0] => 57
[1] => 896
[2] => 2172
[3] => 3428
[4] => 4236
[5] => 4844
[6] => 6524
[7] => 7586
[8] => 8172
[9] => 8650
)
|