PHP鸡尾酒（Cocktail）排序算法的实现（代码示例）

来源：藏色散人 发布时间：2019-03-11 11:44:44 阅读量：1080

鸡尾酒排序也称为双向冒泡排序（bidirectional bubble sort）、摇曳排序（shaker sort）、波纹排序（ ripple sort）、洗牌排序（shuffle sort）或穿梭排序（ shuttle sort ）是冒泡排序的一种变体，它既是一种稳定的排序算法，也是一种比较排序。

该算法与冒泡排序的不同之处在于，它在每次遍历列表时都在两个方向进行排序。这种排序算法实际上比冒泡排序更难以实现，并且解决了冒泡排序中的海龟问题。它只提供了微小的性能改进，并没有改善渐近性能; 就像泡沫一样，虽然它在教育中有用，但它没有实际意义。

鸡尾酒排序可视化动图示例如下:

Sorting_shaker_sort_anim.gif

PHP鸡尾酒排序代码示例如下：

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

<?php

function cocktailSort($my_array)

{

    if (is_string($my_array))

        $my_array = str_split(preg_replace('/\s+/','',$my_array));

 

    do{

        $swapped = false;

        for($i=0;$i<count($my_array);$i++){

            if(isset($my_array[$i+1])){

                if($my_array[$i] > $my_array[$i+1]){

                    list($my_array[$i], $my_array[$i+1]) = array($my_array[$i+1], $my_array[$i]);

                    $swapped = true;

                }

            }

        }

 

        if ($swapped == false) break;

 

        $swapped = false;

        for($i=count($my_array)-1;$i>=0;$i--){

            if(isset($my_array[$i-1])){

                if($my_array[$i] < $my_array[$i-1]) {

                    list($my_array[$i],$my_array[$i-1]) = array($my_array[$i-1],$my_array[$i]);

                    $swapped = true;

                }

            }

        }

    }while($swapped);

 

    return $my_array;

}

$test_array = array(3, 0, 2, 5, -1, 4, 1);

echo "原始数组:\n";

echo implode(', ',$test_array );

echo "\n排序后数组\n:";

echo implode(', ',cocktailSort($test_array)). PHP_EOL;

输出：

1

2

原始数组: 3, 0, 2, 5, -1, 4, 1

排序后数组 :-1, 0, 1, 2, 3, 4, 5


标签： PHP
分享：
评论：
你还没有登录，请先

热门标签

热门文章

    推荐文章