计算机科学

首页 > 计算机科学

鸡尾酒排序

2018-08-28 09:42:54     所属分类:排序算法
鸡尾酒排序
Sorting shaker sort anim.gif
使用鸡尾酒排序为一列数字进行排序的过程
分类 排序算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度

鸡尾酒排序,也就是定向冒泡排序鸡尾酒搅拌排序搅拌排序(也可以视作选择排序的一种变形),涟漪排序来回排序快乐小时排序,是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

目录

  • 1 伪代码
  • 2 与冒泡排序不同的地方
  • 3 实现示例
    • 3.1 C语言
    • 3.2 C++
    • 3.3 JAVA
    • 3.4 JavaScript
    • 3.5 PHP
    • 3.6 Python 2.7
  • 4 复杂度
  • 5 额外链接

伪代码

将一个序列由小到大进行排序:

function cocktail_sort(list, list_length){ // the first element of list has index 0
    bottom = 0;
    top = list_length - 1;
    swapped = true; 
    while(swapped == true) // if no elements have been swapped, then the list is sorted
    {
        swapped = false; 
        for(i = bottom; i < top; i = i + 1)
        {
            if(listi > listi + 1)  // test whether the two elements are in the correct order
            {
                swap(listi, listi + 1); // let the two elements change places
                swapped = true;
            }
        }
        // decreases top the because the element with the largest value in the unsorted
        // part of the list is now on the position top 
        top = top - 1; 
        for(i = top; i > bottom; i = i - 1)
        {
            if(listi < listi - 1) 
            {
                swap(listi, listi - 1);
                swapped = true;
            }
        }
        // increases bottom because the element with the smallest value in the unsorted 
        // part of the list is now on the position bottom 
        bottom = bottom + 1;  
    }
}

与冒泡排序不同的地方

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

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

实现示例

C语言

void cocktail_sort(int arr, int len) {
	int i, left = 0, right = len - 1;
	int temp;
	while (left < right) {
		for (i = left; i < right; i++)
			if (arri > arri + 1) {
				temp = arri;
				arri = arri + 1;
				arri + 1 = temp;
			}
		right--;
		for (i = right; i > left; i--)
			if (arri - 1 > arri) {
				temp = arri;
				arri = arri - 1;
				arri - 1 = temp;
			}
		left++;
	}
}

C++

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void cocktail_sort(T arr, int len) {
	int j, left = 0, right = len - 1;
	while (left < right) {
		for (j = left; j < right; j++)
			if (arrj > arrj + 1)
				swap(arrj, arrj + 1);
		right--;
		for (j = right; j > left; j--)
			if (arrj - 1 > arrj)
				swap(arrj - 1, arrj);
		left++;
	}
}

JAVA

public static void cocktail_sort(int arr) {	
	int i, left = 0, right = arr.length - 1;
	int temp;
	while (left < right) {
		for (i = left; i < right; i++)
			if (arri > arri + 1) {
				temp = arri;
				arri = arri + 1;
				arri + 1 = temp;
			}
		right--;
		for (i = right; i > left; i--)
			if (arri - 1 > arri) {
				temp = arri;
				arri = arri - 1;
				arri - 1 = temp;
			}
		left++;
	}
}

JavaScript

Array.prototype.cocktail_sort = function() {
	var i, left = 0, right = this.length - 1;
	var temp;
	while (left < right) {
		for (i = left; i < right; i++)
			if (thisi > thisi + 1) {
				temp = thisi;
				thisi = thisi + 1;
				thisi + 1 = temp;
			}
		right--;
		for (i = right; i > left; i--)
			if (thisi - 1 > thisi) {
				temp = thisi;
				thisi = thisi - 1;
				thisi - 1 = temp;
			}
		left++;
	}
};

PHP

function swap(&$x, &$y) {
	$t = $x;
	$x = $y;
	$y = $t;
}
function cocktail_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參才能修改原陣列
	$left = 0;
	$right = count($arr) - 1;
	while ($left < $right) {
		for ($j = $left; $j < $right; $j++)
			if ($arr$j > $arr$j + 1)
				swap($arr$j, $arr$j + 1);
		$right--;
		for ($j = $right; $j > $left; $j--)
			if ($arr$j - 1 > $arr$j)
				swap($arr$j - 1, $arr$j);
		$left++;
	}
}

Python 2.7

def cocktail_sort(l):
    l_len = len(l)
    for i in xrange(l_len, 0, -1):
        rem_i_l_len = abs(i - l_len)
        isNeedContinue = False
        obverse_count = len(lrem_i_l_len : i-1)
        reverse_count = len(lrem_i_l_len + 1 : i-1)
        
        for j in xrange(obverse_count):
            if lj > lj + 1:
                lj, lj + 1 = lj + 1, lj
                isNeedContinue = True
        # you can print this to observe the whole process
        # print l
        
        for j in xrange(reverse_count, 0, -1):
            if lj < lj - 1:
                lj, lj - 1 = lj - 1, lj
                isNeedContinue = True
        # you can print this to observe the whole process
        # print l
        
        if isNeedContinue:
            continue
        else:
            return
  
        
if __name__ == '__main__':
    sample_list = 6,5,4,3,2,100
    cocktail_sort(sample_list)
    print sample_list

复杂度

鸡尾酒排序最糟或是平均所花费的次数都是,但如果序列在一开始已经大部分排序过的话,会接近

额外链接

  • Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
  • Implementations of cocktail sort in several different programming languages

上一篇:插值排序
下一篇:选择排序
相关推荐