数据结构与算法(php版)排序之鸡尾酒排序

yang-pig| 阅读:524 发表时间:2018-07-26 22:10:15 算法

算法原理为什么叫鸡尾酒排序?其实我也不知道,知道的小伙伴请告诉我。

其实它还有很多奇怪的名称,比如双向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、摇曳排序 (Shuffle Sort)、飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort)。本文中就以鸡尾酒排序来称呼它。

鸡尾酒排序是冒泡排序的轻微变形。不同的地方在于,鸡尾酒排序是从低到高然后从高到低来回排序,而冒泡排序则仅从低到高去比较序列里的每个元素。他可比冒泡排序的效率稍微好一点,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问一次序列就可以完成排序,但如果使用冒泡排序则需要四次。但是在乱数序列状态下,鸡尾酒排序与冒泡排序的效率都很差劲,优点只有原理简单这一点。

排序过程:

先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端

再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端

以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束

sorting-shaker-sort-anim.gif

实例分析

以数组 array = [45, 19, 77, 81, 13, 28, 18, 19, 77] 为例,排序过程如下:

从左到右,找到最大的数 81,放到数组末尾:

┌─────────────────────────────────────────┐
│  19   45   77   13   28   18   19   7781
└─────────────────────────────────────────┘

从右到左,找到剩余数组(先框中的部分)中最小的数 ,放到数组开头:

    ┌────────────────────────────────────┐
1319   45   77   18   28   19   7781
    └────────────────────────────────────┘

从左到右,在剩余数组中找到最大数,放在剩余数组的末尾:

    ┌───────────────────────────────┐
1319   45   18   28   18   7777   81
    └───────────────────────────────┘

从右到左

         ┌──────────────────────────┐
13   1819   45   18   28   7777   81
         └──────────────────────────┘

从左到右

         ┌─────────────────────┐
13   1819   18   28   4577   77   81
         └─────────────────────┘

从右到左

              ┌────────────────┐
13   18   1819   28   4577   77   81
              └────────────────┘

从左到右

              ┌───────────┐
13   18   1819   2845   77   77   81
              └───────────┘

从右到左

                   ┌──────┐
13   18   18   192845   77   77   81
                   └──────┘



<?php
/**
 * 鸡尾酒排序:
 * 为什么叫鸡尾酒排序?其实我也不知道,知道的小伙伴请告诉我。
 * 其实它还有很多奇怪的名称,比如双向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、
 * 摇曳排序 (Shuffle Sort)、飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort)。
 * 本文中就以鸡尾酒排序来称呼它。
 *----------------------------------------------------------------------------
 * 鸡尾酒排序是冒泡排序的轻微变形。不同的地方在于,鸡尾酒排序是从低到高然后从高到低来回排序,
 * 而冒泡排序则仅从低到高去比较序列里的每个元素。他可比冒泡排序的效率稍微好一点,
 * 原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。
 */
/**
 * @param array $data
 * @return array
 */
function ShuttleSort(array $data) {
    $swap = function (array &$data,$i,$j) {
        $temp     = $data[$i];
        $data[$i] = $data[$j];
        $data[$j] = $temp;
        return $data;
    };
    $count = count($data);
    $left = 0;
    $right = $count - 1;
    while ($left < $right) {
        //从左到右
        $lastRight = 0;
        for ($i = $left;$i < $right;$i++) {
            if ($data[$i] > $data[$i + 1]) {
                $swap($data,$i,$i + 1);
                $lastRight = $i;
            }
        }
        $right = $lastRight;
        // 从右到左
        $lastLeft = 0;
        for ($j = $right;$left < $j;$j--) {
            if ($data[$j - 1] > $data[$j]) {
                $swap($data, $j - 1, $j);
                $lastLeft = $j;
            }
        }
        $left = $lastLeft;
    }
    return $data;

}
var_dump(ShuttleSort([6, 13, 21, 99, 18, 2, 25, 33, 19, 84]));

1 (2).png

2.png

3.png