冒泡排序是几乎是面试和稍懂点算法以及资深人士的口头禅，身为程序员，你要是不知道这个排序，就会被严重鄙视的。笔者以前也不会这个排序，更不知道这个排序有什么卵用，但听那么多高手和大牛说这些基础很重要，也就硬着头皮啃了，毕竟多学习一丁点东西，总归没什么害处。
概念
冒泡排序 - Bubble 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
| <?php
class BubbleSort
{
/**
* 主运行方法
*
* @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++) {
for ($j = 0; $j < $count - $i - 1; $j++) {
if (self::compare($array[$j], $array[$j + 1]) > 0) {
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) {
$x ^= $y;
$y ^= $x;
$x ^= $y;
}
}
/**
* 生成随机数组
*
* @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;
}
}
BubbleSort::main();
// 结果
Array
(
[0] => 9
[1] => 656
[2] => 755
[3] => 879
[4] => 3578
[5] => 3812
[6] => 5139
[7] => 6412
[8] => 8804
[9] => 9458
)
|
方案二
标志变量用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换，说明序列已经有序了，不必继续进行下去了
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 BubbleSort
{
/**
* 主运行方法
*
* @return void
*/
public static function main(): void
{
$random = self::random(100, 200);
$array = self::sort($random);
print_r($array);
}
/**
* 冒泡排序
*
* @param array $array
*
* @return array
*/
public static function sort(array &$array): array
{
$count = count($array);
$isSwapped = true;
for ($i = 0; $i < $count && $isSwapped === true; $i++) {
$isSwapped = false;
for ($j = 0; $j < $count - $i - 1; $j++) {
if (self::compare($array[$j], $array[$j + 1]) > 0) {
self::swap($array[$j], $array[$j + 1]);
$isSwapped = true;
}
}
}
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;
}
}
BubbleSort::main();
// 结果
Array
(
[0] => 129
[1] => 140
[2] => 141
[3] => 150
[4] => 152
[5] => 159
[6] => 165
[7] => 175
[8] => 191
[9] => 199
)
|
方案三
技巧
鸡尾酒排序 - Cocktail 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
109
110
111
112
113
| <?php
class CocktailSort
{
/**
* 主运行方法
*
* @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
{
$left = 0;
$right = count($array) - 1;
while ($left < $right) {
for ($j = $left; $j < $right; $j++) {
if (self::compare($array[$j], $array[$j + 1]) > 0) {
self::swap($array[$j], $array[$j + 1]);
}
}
$right--;
for ($j = $right; $j > $left; $j--) {
if (self::compare($array[$j], $array[$j + 1]) > 0) {
self::swap($array[$j], $array[$j + 1]);
}
}
$left++;
}
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;
}
}
CocktailSort::main();
// 结果
Array
(
[0] => 4596
[1] => 2439
[2] => 3177
[3] => 3424
[4] => 6605
[5] => 6629
[6] => 7526
[7] => 8666
[8] => 8854
[9] => 9986
)
|