论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2011-11-24 14:15 |只看该作者 |倒序浏览

PHP实现各种排序

Php代码

1.<?php
2./**
3. * 各种排序
4. * @author zhaojaingwei
5. * @since 2011/11/21 16:14
6. *
7. */
8.
9.$list = array(3,5,1,2,10,8,15,19,20);
10.
11.//快排
12.function fast(&$list, $low, $high){
13. if($high - $low > 5){
14. while($low < $high){
15. $key = excute($list, $low, $high);
16. fast($list, $low, $key - 1);
17. //fast($list, $key + 1, $high);//普通递归实现
18. $low = $key + 1;//尾递归实现
19. }
20. }else{
21. insert($list);
22. }
23.}
24.
25.//快排执行一次排序
26.function excute(&$list, $low, $high){
27. swap($list, $low, ($low + $high)/2);
28. $temp = $list[$low];
29. while($low < $high){
30. while($low < $high && $list[$high] > $temp){
31. $high --;
32. }
33.
34. $list[$low] = $list[$high];
35.
36. while($low < $high && $list[$low] < $temp){
37. $low ++;
38. }
39.
40. $list[$high] = $list[$low];
41. }
42.
43. $list[$low] = $temp;
44.
45. return $low;
46.}
47.
48.//堆排序
49.function heap(&$list){
50. buildHeap($list);
51. for($i = count($list) - 1; $i > 0; $i --){
52. swap($list, $i, 0);
53. heapfy($list, 0, $i - 1);
54. }
55.}
56.
57.//创建堆
58.function buildHeap(&$list){
59. for($i = (count($list) - 2)/2; $i >= 0; $i --){
60. heapfy($list, $i, count($list) - 1);
61. }
62.}
63.
64.//维护堆
65.function heapfy(&$list, $low, $high){
66. $temp = $list[$low];
67.
68. for($i = ($low * 2 + 1); $i <= $high; $i = ($i * 2 + 1)){
69. if($i < $high && $list[$i] < $list[$i + 1]){
70. $i ++;
71. }
72.
73. if($temp < $list[$i]){
74. swap($list, $i, $low);
75. $low = $i;
76. }else{
77. break;
78. }
79.
80. }
81.
82. $list[$low] = $temp;
83.}
84.
85.//希尔排序
86.function shell(&$list){
87. $a = 0;
88. $code = count($list)/3 + 1;
89. while($code >= 1){
90. for($i = $code; $i < count($list); $i ++){
91. $a ++;
92. if($list[$i] < $list[$i - $code]){
93. $temp = $list[$i];
94. $list[$i] = $list[$i - $code];
95. $j = $i - 2*$code;
96.
97. for(; $j >= 0 && $list[$j] > $temp; $j -= $code){
98. $list[$j + $code] = $list[$j];
99. $a ++;
100. }
101. $list[$j + $code] = $temp;
102. }
103. }
104.
105. $code = $code/3;
106. }
107.
108. echo $a;
109.}
110.
111.//直接插入排序
112.function insert(&$list){
113. $a = 0;
114. for($i = 1; $i < count($list); $i ++){
115. $a ++;
116. if($list[$i] < $list[$i - 1]){
117. $temp = $list[$i];
118. $list[$i] = $list[$i - 1];
119.
120. $j = $i - 2;
121. for(; $list[$j] > $temp; $j --){
122. $a ++;
123. $list[$j + 1] = $list[$j];
124. }
125.
126. $list[$j + 1] = $temp;
127. }
128. }
129.
130. echo $a;
131.}
132.
133.//简单选择排序
134.function select(&$list){
135. $a = 0;
136. for($i = 0; $i < count($list); $i ++){
137. $min = $i;
138. $a ++;
139. for($j = $i + 1; $j < count($list); $j ++){
140. $a ++;
141. if($list[$j] < $list[$min]){
142. $min = $j;
143. }
144. }
145.
146. if($min != $i)
147. swap($list, $i, $min);
148. }
149. echo $a;
150.}
151.
152.//冒泡排序
153.function bubble(&$list){
154. $swap = TRUE;
155. $a = 0;
156. for($i = 0; $i < count($list) && $swap; $i ++){
157. $swap = FALSE;
158. $a ++;
159. for($j = count($list) - 2; $j >= $i; $j --){
160. $a ++;
161. if($list[$j] > $list[$j + 1]){
162. $swap = TRUE;
163. swap($list, $j, $j + 1);
164. }
165. }
166. }
167. echo $a;
168.}
169.
170.//移动或交换函数
171.function swap(&$list, $i, $j){
172. $temp = $list[$i];
173. $list[$i] = $list[$j];
174. $list[$j] = $temp;
175.}
176.
177.?>

复制代码

php

文库|博客

返回列表

Chinaunix › 论坛 › 程序设计 › PHP › php文档中心 › PHP实现各种排序

PHP实现各种排序 [复制链接]