冒泡排序（Bubble Sort），是一种较简单的、稳定的排序算法。冒泡排序算法步骤：比较相邻的元素，如果第一个比第二个大，就交换他们两个的位置；对每对相邻的元素执行同样的操作，这样一趟下来，最后的元素就是最大的；除了已得出来的最大元素，把剩余的元素重复前面步骤，直到没有元素再需要比较为止，这样排序就完成了。冒泡算法，在最好情况下，时间复杂度为O(n)；在最坏情况下，时间复杂度为O(n2)；平均时间复杂度为O(n2)。
|
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
|
<?php/** * 数据结构与算法（PHP实现） - 冒泡排序（Bubble Sort）。
*
* @author 创想编程（TOPPHP.ORG）
* @copyright Copyright (c) 2013 创想编程（TOPPHP.ORG） All Rights Reserved
* @license http://www.opensource.org/licenses/mit-license.php MIT LICENSE
* @version 1.0.0 - Build20130608
*/
class BubbleSort {
/**
* 冒泡排序。
*
* @var integer
*/
const SORT_NORMAL = 1;
/**
* 双向冒泡排序。
*
* @var integer
*/
const SORT_DUPLEX = 2;
/**
* 需要排序的数据数组。
*
* @var array
*/
private $data ;
/**
* 数据数组的长度。
*
* @var integer
*/
private $size ;
/**
* 数据数组是否已排序。
*
* @var boolean
*/
private $done ;
/**
* 构造方法 - 初始化数据。
*
* @param array $data 需要排序的数据数组。
*/
public function __construct( array $data ) {
$this ->data = $data ;
$this ->size = count ( $this ->data);
$this ->done = FALSE;
}
/**
* 交换数据数组中两个元素的位置。
*
* @param integer $x 元素在数组中的索引。
* @param integer $y 元素在数组中的索引。
*/
private function swap( $x , $y ) {
$temp = $this ->data[ $x ];
$this ->data[ $x ] = $this ->data[ $y ];
$this ->data[ $y ] = $temp ;
}
/**
* 冒泡排序。
*/
private function sort() {
$this ->done = TRUE;
for ( $i = 1; $i < $this ->size; ++ $i ) {
// 记录交换数据的次数。
$swap = 0;
for ( $j = $this ->size - 1; $j > $i - 1; -- $j ) {
if ( $this ->data[ $j ] < $this ->data[ $j - 1]) {
$this ->swap( $j - 1, $j );
++ $swap ;
}
}
// 若交换数据的次数为0，说明数据数组已有序，不必再进行排序。
if (0 === $swap ) {
break ;
}
}
}
/**
* 双向冒泡排序。
*/
private function duplexSort() {
$this ->done = TRUE;
for ( $i = 1; $i <= floor ( $this ->size / 2); ++ $i ) {
// 记录交换数据的次数。
$swap = 0;
for ( $j = $this ->size - 1, $k = $i - 1;
$j > $i - 1 && $k < $this ->size - 1; -- $j , ++ $k ) {
if ( $this ->data[ $j ] < $this ->data[ $j - 1]) {
$this ->swap( $j - 1, $j );
++ $swap ;
}
if ( $this ->data[ $k ] > $this ->data[ $k + 1]) {
$this ->swap( $k , $k + 1);
++ $swap ;
}
}
// 若交换数据的次数为0，说明数据数组已有序，不必再进行排序。
if (0 === $swap ) {
break ;
}
}
}
/**
* 获取排序后的数据数组。
*
* @param integer $sort 排序算法：SORT_NORMAL为冒泡排序；SORT_DUPLEX为双向冒泡排序。
* @return array 返回排序后的数据数组。
*/
public function getResult( $sort = self::SORT_NORMAL) {
// 若已排序则无需再进行排序，直接返回排序好的数据数组。
if ( $this ->done) {
return $this ->data;
}
switch ( $sort ) {
case self::SORT_DUPLEX:
$this ->duplexSort();
break ;
case self::SORT_NORMAL:
default :
$this ->sort();
break ;
}
return $this ->data;
}
}?> |
|
1
2
3
4
|
<?php$bubble = new BubbleSort( array (35, 75, 92, 41, 27, 58));
echo '<pre>' , print_r( $bubble ->getResult(BubbleSort::SORT_DUPLEX), TRUE), '</pre>' ;
?> |