常见排序算法11——鸡尾酒排序

鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

算法描述

数组中的数字本是无规律的排放，先找到最大的数字，把他放到最后一位，然后找到最小的数字放到第一位。然后再找到第二大的数字放到倒数第二位，再找到第二小的数字放到第二位。以此类推。

1）从待排序列左侧第一个元素开始，比较相邻的元素。如果左边比右边元素大，就交换它们两个，直到最大的元素排到序列最右侧

2）再从待排序列最右侧元素开始（除去已排序的最右侧元素），比较相邻元素，如果右侧比左侧元素大，就交换两个元素，直到最小元素排到序列最左边；

3）对剩余的待排元素（最左和最右元素已经有序）重复1，2两步，直到排序完成；

算法实现

PHP代码

算法性能分析

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：同冒泡排序法一样，鸡尾酒排序是稳定的