CodeSky 代码之空

随手记录自己的学习过程

PHP实现冒泡排序

2014-01-25 20:10分类: PHP评论: 0

冒泡排序，所有语言中的基础排序方法OTZ（画外音：那为什么你总是忘了冒泡排序的原理勒）

百度百科介绍：

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再?> 需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。

介绍2：

冒泡排序算法的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

当然我最终还是没有看懂，让我看懂的是……我看了课件上的一张图……

没错，就是一个个浮到最后，也就是说固定的是最后一个，变化的是终值，而初值从零开始。

核心算法：

1	$counter = count($array);
2	
3	for ($i=0; $i < $counter -1; $i++) { 
4		for ($j = 0; $j < $counter - $i - 1; $j++) { 
5			if ($array[$j] > $array[$j + 1]) {
6				list($array[$j], $array[$j + 1]) = array($array[$j + 1], $array[$j]);
7			}
8		}
9		
10	}
11

这里没有引入第三个变量，而是使用了list()，关于list()，之前有一篇：http://codesky.me/archives/php-list-exchange.wind

这里大的往后浮动，也就是说是从小到大排序 当然，php的自带排序是快速排序，效率要高的多，所以不用自写排序，但其他语言可能还是需要的。

演示

完整代码：

1<!DOCTYPE html>
2<html>
3<head>
4	<meta charset="utf-8">
5	<title></title>
6</head>
7<body>
8	<h1>冒泡排序</h1>
9	<form action="pop.php" method="post">
10		<input type="text" name="array" placeholder="输入数字，用空格分割">
11		<input type="hidden" name="shot" value="shot">
12		<input type="submit" value="提交">
13	</form>
14
15	<?php
16		if (!empty($_POST['shot'])) {
17			$problem = FALSE;
18			$input = $_POST['array'];
19
20			if (empty($input)) {
21				echo '请输入数字';
22				$problem = TRUE;
23			} else {
24				$array = explode(' ', $input);
25				$array = clean_empty_element($array);
26				foreach ($array as $key => $value) {
27					if (!is_numeric($value)) {
28						echo '<( ￣^￣)>你确定你输入的是阿拉伯数字吗';
29						$problem = TRUE;
30						break;
31					}
32				}
33			}
34			
35			if (!$problem) {
36				$counter = count($array);
37				
38				for ($i=0; $i < $counter -1; $i++) { 
39					for ($j = 0; $j < $counter - $i - 1; $j++) { 
40						if ($array[$j] > $array[$j + 1]) {
41							list($array[$j], $array[$j + 1]) = array($array[$j + 1], $array[$j]);
42						}
43					}
44					
45				}
46
47				print_r($array);
48			}
49		}
50
51		function clean_empty_element($array) {
52			foreach ($array as $key => $value) {
53				if ($value == '') {
54					unset($array[$key]);
55				}
56			}
57
58			$array = array_values($array);
59			return $array;
60		}
61	?>
62</body>
63</html>
64

这里也用到了一个自己写的函数，鉴于本篇主要写冒泡，而且其他时候还会用到，所以以后再做介绍

评论 (0)