用php实现几种常见的排序算法

用php实现几种常见的排序算法（代码实例）

一、冒泡排序

冒泡排序理解起来是最简单，但是时间复杂度(0(n~2))也是最大的之一，实现代码如

下：

lfunctionbubbleSort($arr){

2$len=count($arr);

3for($i=0;$i<$len;$i++){

4/／遍历i后面的元素，只要该元素小于当前元素，就把较小的往前冒泡

5for($j=$i+1;$j<$len;$j++){

6if($arr[$i]>$arr[$j]){

7$t=$arr[$i];

8$arr[$i]=$arr[$j];

9$arr[$j]=$t;

10}

11}

12}

13return$arr;

14}

15

16$arr=[3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];

17print_r(bubbleSort($arr));

二、选择排序

选择排序理解起来也比较简单，时间复杂度也是O(n'2)，实现代码如下：

lfunctionselectSort($arr){

2$len=count($arr);

3for($i=0;$i<$len;$i++){

4$minindex=$i;

5/／找出i丿5面最小的元素与当前元素交换

6for($j=$i+1;$j<$len;$j++){

7if($arr[$j]<$arr[$minindex]){

8$minindex=$j;

9}

10}

11if($minindex!=$i){

12$t=$arr[$i];

13$arr[$i]=$arr[$minindex];

14$arr[$minindex]=$t;

15}

16}

17return$arr;

18}

19$arr=[3,1,13,S,7,11,2,4,14,9,15,6,12,10,8];

20print_r(bubbleSort($arr));

三、插入排序

感觉插入排序跟冒泡排序有点相似，时间复杂度也是O(n·2)，实现代码如下：

lfunctioninsertSort($arr){

2$len=count($arr);

3for($i=1;$i<$len;$i++){

4if($arr[$i]<$arr[$i-1]){

5$t=$arr[$i];

6$j=$i-1;

7/／如果当前元素大千前一个元素，就往前挪

8while($j>=0&&$t<$arr[$j]){

9$arr[$j+1]=$arr[$j];

10$j--;

11}

12$arr[$j+1]=$t;

13}

14}

15return$arr;

16}

17

18$arr=[3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];

19print_r(bubbleSort($arr));

四、希尔排序

希尔排序其实可以理解是插入排序的一个优化版，它的效率跟增量有关，增量要取多少，

根据不同的数组是不同的，所以希尔排序是一个不稳定的排序算法，它的时间复杂度为

O(nlogn)到O(n·2)之间，实现代码如下：

lfunctionshel1Sort($arr){

2$len=count($arr);

3$stepSize=floor($len/2);

4while($stepSize>=1){

5for($i=$stepSize;$i<$len;$i++){

6if($arr[$i]<$arr[$i-$stepSize]){

7$t=$arr[$i];

8$j=$i-$stepSize;

9while($j>=0&&$t<$arr[$j]){

10$arr[$j+$stepSize]=$arr[$j];

11$j-=$stepSize;

12}

13$arr[$j+$stepSize]=$t;

14}

15}

16/／缩小步长，再进行插入排序

17$stepSize=floor($stepSize/2);

18}

19return$arr;

20}

21

22$arr=[3,1,13,S,7,11,2,4,14,9,15,6,12,10,8];

23print_r(bubbleSort($arr));

五、堆排序

堆排序是一种高效的排序算法，它的时间复杂度是O(nlogn)。原理是：先把数组转为

一个最大堆，然后把第一个元索跟第1元素交换，然后把剩下的i-1个元素转为最大堆，然

后再把第一个元素与第i-1个元素交换，以此类推。实现代码如下：

lfunctionheapSort($arr){

2$len=count($arr);

3/／先建立蔽大堆

4for($i=floor(($len-1)/2);$i>=0;$i--){

5$s=$i;

6$childindex=$s*2+1;

7while($childindex<$len){

8/／在父、左子、右子中，找到最大的

9if($childindex+1<$len&&$arr[$childindex]<$arr[$childindex+1])

10$childindex++;

llif($arr[$s]<$arr[$childindex]){

12$t=$arr[$s];

13$arr[$s]=$arr[$childindex];

14$arr[$childindex]=$t;

15$s=$childindex;

16$childindex=$childindex*2+1;

17}else{

18break;

19}

20}

21}

22/／从最后一个元素开始调整

23for($i=$len-1;$i>0;$i--){

24$t=$arr[$i];

25$arr[$i]=$arr[0);

26$arr[0)=$t;

27/／调整第一个元素

28$s=0;

29$childlndex=1;

30while($childlndex<$i){

31/／在父、左子、右子中，找到蔽大的

32if($childlndex+1<$i&&$arr[$childlndex]<$arr[$childlndex+1))

33$childindex++;

34if($arr[$s]<$arr[$childlndex]){

35$t=$arr[$s];

36$arr[$s)=$arr[$childlndex];

37$arr[$childlndex]=$t;

38$s=$childlndex;

39$childlndex=$childlndex*2+1;

40}else{

41break;

42}

43}

44}

45return$arr;

46}

47

$arr=[3,1,13,S,7,11,2,4,14,9,15,6,12,10,8];

print_r(bubbleSort($arr));

六、快速排序

快排也是一个高效的排序算法，它的时间复杂度也是O(nlogn)。原理是：选择一个基

准元索，然后把数组中小于这个元素的元素放在基准元素左边，大于它的，放在基准元素右

边。然后对这两边继续同样的操作。代码如下：

lfunctionquickSort($arr){

2$len=count($arr);

3quickSortRecursion($arr,0,$len-1);

4return$arr;

5}

6

7functionquickSortRecursion(&$arr,$begin,$end){

8if($begin<$end){

9$left=$begin;

10$right=$end;

11$temp=$arr[$begin];//$temp为某准元素

12/／把小千＄temp的元素放到＄temp左边，大千它的放在右边

13while($left<$right){

14while($left<$right&&$arr[$right]>=$temp)$right--;

15if($left<$right){

16$arr[$left++]=$arr[$right];

17}

18while($left<$right&&$arr[$left]<=$temp)$left++;

19if($left<$right){

20$arr[$right--]=$arr[$left];

21}

22}

23$arr[$left]=$temp;

24/／把数组分成两部分，递归调用该函数

25quickSortRecursion($arr,$begin,$left-1);

26quickSortRecursion($arr,$left+1,$end);

27}

28return$arr;

29}

30

31$arr=[3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];

32print_r(bubbleSort($arr));

七、归并排序

归并排序的时间复杂度也是O(nlogn)。原理是：对千两个排序好的数组，分别遍历这

两个数组，获取较小的元素插入新的数组巾，那么，这么新的数组也会是排序好的。代码如

下：

lfunctionmergeSort($arr){

2$len=count($arr);

3$arr=mergeSortRecursion($arr,0,$len-1);

4return$arr;

5}

6

7functionmergeSortRecursion(&$arr,$begin,$end){

8if($begin<$end){

9$mid=floor(($begin+$end)/2);

10/／把数组不断拆分，只到只剩下一个元素，对于一个元素的数组，一定是排序好的

11mergeSortRecursion($arr,$begin,$mid);

12mergeSortRecursion($arr,$mid+1,$end);

13$i=