鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
算法描述
数组中的数字本是无规律的排放,先找到最大的数字,把他放到最后一位,然后找到最小的数字放到第一位。然后再找到第二大的数字放到倒数第二位,再找到第二小的数字放到第二位。以此类推。
1)从待排序列左侧第一个元素开始,比较相邻的元素。如果左边比右边元素大,就交换它们两个,直到最大的元素排到序列最右侧
2)再从待排序列最右侧元素开始(除去已排序的最右侧元素),比较相邻元素,如果右侧比左侧元素大,就交换两个元素,直到最小元素排到序列最左边;
3)对剩余的待排元素(最左和最右元素已经有序)重复1,2两步,直到排序完成;
算法实现
PHP代码
算法性能分析
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:同冒泡排序法一样,鸡尾酒排序是稳定的
领取专属 10元无门槛券
私享最新 技术干货