1.冒泡算法,排序算法,由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序,实例代码如下:

1. $array = array(a,f,c,b,e,h,j,i,g);  
2. //开源代码phpfensi.com 
3.    function maopao_fun($array){  
4.  
5.        if($len <= 1) {  
6.  
7.            return $arr;  
8.  
9.        }  
10.  
11.        $count = count($array);  
12.  
13.        for($i=0;$i<$count;$i++){  
14.  
15.            for($j=$count-1;$j>$i;$j--){  
16.  
17.                if($array[$j] > $array[$j-1]){  
18.  
19.                    $tmp = $array[$j];  
20.  
21.                    $array[$j] = $array[$j-1];  
22.  
23.                    $array[$j-1] = $tmp;  
24.  
25.                }  
26.  
27.            }  
28.  
29.        }  
30.  
31.        return $array;  
32.  
33.    }  

2.快速排序

快速排序（Quicksort）是对冒泡排序的一种改进,由C. A. R. Hoare在1962年提出,它的基本思想是,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行.以此达到整个数据变成有序序列,实例代码如下:

1. function quickSort($arr){  
2.  
3.        $len = count($arr);  
4.  
5.        if($len <= 1) {  
6.  
7.            return $arr;  
8.  
9.        }  
10.  
11.        $key = $arr[0];  
12.  
13.        $left_arr    = array();  
14.  
15.        $right_arr    = array();  
16.  
17.        for($i=1; $i<$len; $i++){  
18.  
19.            if($arr[$i] <= $key){  
20.  
21.                $left_arr[] = $arr[$i];  
22.  
23.            } else {  
24.  
25.                $right_arr[] = $arr[$i];  
26.  
27.            }  
28.  
29.        }  
30.  
31.        $left_arr    = quickSort($left_arr);  
32.  
33.        $right_arr    = quickSort($right_arr);  
34.  
35.        return array_merge($left_arr, array($key), $right_arr);  
36.  
37.    }  

3.选择排序

每一趟从待排序的数据元素中选出最小或最大的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完,选择排序是不稳定的排序方法,代码如下:

1. function select_sort($arr){  
2.  
3.     $count = count($arr);  
4.  
5.     for($i=0; $i<$count; $i++){  
6.  
7.         for($j=$i+1; $j<$count; $j++){  
8.  
9.             if ($arr[$i] > $arr[$j]){  
10.  
11.                 $tmp = $arr[$i];  
12.  
13.                 $arr[$i] = $arr[$j];  
14.  
15.                 $arr[$j] = $tmp;  
16.  
17.             }  
18.  
19.         }  
20.  
21.     }  
22.  
23.     return $arr;  
24.  
25. }  

4.插入排序

从第一个元素开始,该元素可以认为已经被排序,取出下一个元素,在已经排序的元素序列中从后向前扫描,如果该元素（已排序）大于新元素,将该元素移到下一位置,重复步骤3,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到下一位置中,重复步骤2,代码如下:

1. function insert_sort($arr){  
2.  
3.         $count = count($arr);  
4.  
5.         for($i=1; $i<$count; $i++){  
6.  
7.             $tmp = $arr[$i];  
8.  
9.             $j = $i - 1;  
10.  
11.             while($arr[$j] > $tmp){  
12.  
13.                 $arr[$j+1] = $arr[$j];  
14.  
15.                 $arr[$j] = $tmp;  
16.  
17.                 $j--;  
18.  
19.             }  
20.  
21.         }  
22.  
23.         return $arr;  
24.  
25.     }  
26.  
27.  
28.     $arr = array(49,38,65,97,76,13,27);  
29.  
30.     print_r(insert_sort($arr)); 

四种排序算法的PHP实现

1) 插入排序(Insertion Sort)的基本思想是:

每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止.

2) 选择排序(Selection Sort)的基本思想是:

每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕.

3) 冒泡排序的基本思想是:

两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止.

4) 快速排序实质上和冒泡排序一样,都是属于交换排序的一种应用,所以基本思想和上面的冒泡排序是一样的,代码如下:

1. <?php 
2. /** 
3.  *  
4.  * @author quanshuidingdang 
5.  */ 
6. class Sort { 
7.  private $arr  = array();  
8.  private $sort = 'insert'; 
9.  private $marker = '_sort'; 
10.  
11.  private $debug = TRUE; 
12.  
13.  /** 
14.   * 构造函数 
15.   * 
16.   * @param array 例如： $config = array ( 
17.          'arr' => array(22,3,41,18) ,  //需要排序的数组值 
18.          'sort' => 'insert',      //可能值: insert, select, bubble, quick 
19.          'debug' => TRUE        //可能值: TRUE, FALSE 
20.          ) 
21.   */ 
22.  public function __construct($config = array()) { 
23.   if ( count($config) > 0) { 
24.    $this->_init($config); 
25.   } 
26.  } 
27.  
28.  /** 
29.   * 获取排序结果 
30.   */ 
31.  public function display() { 
32.   return $this->arr; 
33.  } 
34.  
35.  /** 
36.   * 初始化 
37.   * 
38.   * @param array 
39.   * @return  bool 
40.   */ 
41.  private function _init($config = array()) { 
42.   //参数判断 
43.   if ( !is_array($config) OR count($config) == 0) { 
44.    if ($this->debug === TRUE) { 
45.     $this->_log("sort_init_param_invaild"); 
46.    } 
47.    return FALSE; 
48.   } 
49.    
50.   //初始化成员变量 
51.   foreach ($config as $key => $val) { 
52.    if ( isset($this->$key)) { 
53.     $this->$key = $val; 
54.    } 
55.   } 
56.    
57.   //调用相应的成员方法完成排序 
58.   $method = $this->sort . $this->marker; 
59.   if ( ! method_exists($this, $method)) { 
60.    if ($this->debug === TRUE) { 
61.     $this->_log("sort_method_invaild"); 
62.    } 
63.    return FALSE; 
64.   } 
65.    
66.   if ( FALSE === ($this->arr = $this->$method($this->arr))) 
67.    return FALSE; 
68.   return TRUE; 
69.  } 
70.  
71.  /** 
72.   * 插入排序 
73.   *  
74.   * @param array 
75.   * @return bool 
76.   */ 
77.  private function insert_sort($arr) { 
78.   //参数判断 
79.   if ( ! is_array($arr) OR count($arr) == 0) { 
80.    if ($this->debug === TRUE) { 
81.     $this->_log("sort_array(insert)_invaild"); 
82.    } 
83.    return FALSE; 
84.   } 
85.    
86.   //具体实现 
87.   $count = count($arr); 
88.   for ($i = 1; $i < $count; $i++) { 
89.    $tmp = $arr[$i]; 
90.    for($j = $i-1; $j >= 0; $j--) {  
91.     if($arr[$j] > $tmp) { 
92.      $arr[$j+1] = $arr[$j]; 
93.      $arr[$j] = $tmp; 
94.     } 
95.    } 
96.   } 
97.   return $arr; 
98.  } 
99.  
100.  /** 
101.   * 选择排序 
102.   *  
103.   * @param array 
104.   * @return bool 
105.   */ 
106.  private function select_sort($arr) { 
107.   //参数判断 
108.   if ( ! is_array($arr) OR count($arr) == 0) { 
109.    if ($this->debug === TRUE) { 
110.     $this->_log("sort_array(select)_invaild"); 
111.    } 
112.    return FALSE; 
113.   } 
114.    
115.   //具体实现 
116.   $count = count($arr); 
117.   for ($i = 0; $i < $count-1; $i++) { 
118.    $min = $i; 
119.    for ($j = $i+1; $j < $count; $j++) { 
120.     if ($arr[$min] > $arr[$j])  $min = $j; 
121.    } 
122.    if ($min != $i) { 
123.     $tmp = $arr[$min]; 
124.     $arr[$min] = $arr[$i]; 
125.     $arr[$i] = $tmp; 
126.    } 
127.   } 
128.   return $arr; 
129.  } 
130.  
131.  /** 
132.   * 冒泡排序 
133.   *  
134.   * @param array 
135.   * @return bool 
136.   */ 
137.  private function bubble_sort($arr) { 
138.   //参数判断 
139.   if ( ! is_array($arr) OR count($arr) == 0) { 
140.    if ($this->debug === TRUE) { 
141.     $this->_log("sort_array(bubble)_invaild"); 
142.    } 
143.    return FALSE; 
144.   } 
145.    
146.   //具体实现 
147.   $count = count($arr); 
148.   for ($i = 0; $i < $count; $i++) { 
149.    for ($j = $count-1; $j > $i; $j--) { 
150.     if ($arr[$j] < $arr[$j-1]) { 
151.      $tmp = $arr[$j]; 
152.      $arr[$j] = $arr[$j-1]; 
153.      $arr[$j-1] = $tmp; 
154.     } 
155.    } 
156.   } 
157.   return $arr;  
158.  } 
159.  
160.  /** 
161.   * 快速排序 
162.   *  
163.   * @param array 
164.   * @return bool 
165.   */ 
166.  private function quick_sort($arr) { 
167.   //具体实现 
168.   if (count($arr) <= 1) return $arr;  
169.   $key = $arr[0]; 
170.   $left_arr = array(); 
171.   $right_arr = array(); 
172.   for ($i = 1; $i < count($arr); $i++){ 
173.    if ($arr[$i] <= $key) 
174.     $left_arr[] = $arr[$i]; 
175.    else 
176.     $right_arr[] = $arr[$i]; 
177.   } 
178.   $left_arr = $this->quick_sort($left_arr); 
179.   $right_arr = $this->quick_sort($right_arr); 
180.  
181.   return array_merge($left_arr, array($key), $right_arr); 
182.  } 
183.  
184.  /** 
185.   * 日志记录 
186.   */ 
187.  private function _log($msg) { 
188.   $msg = 'date[' . date('Y-m-d H:i:s') . '] ' . $msg . 'n'; 
189.   return @file_put_contents('sort_err.log', $msg, FILE_APPEND); 
190.  } 
191. } 
192.  
193. /*End of file sort.php*/ 
194. /*Location htdocs/sort.php */ 
195. ?> 

Tags: php排序算法 php算法

分享到：