鸡尾酒排序

维基百科,自由的百科全书
跳转至: 导航搜索
鸡尾酒排序
Sorting shaker sort anim.gif
使用鸡尾酒排序為一列数字进行排序的过程
分類 排序算法
數據結構 数组
最差時間複雜度  O(n^2)
最優時間複雜度 O(n)
平均時間複雜度   O(n^2)

鸡尾酒排序,也就是定向冒泡排序雞尾酒攪拌排序攪拌排序(也可以視作選擇排序的一種變形),漣漪排序來回排序or 快乐小時排序,是冒泡排序的一種变形。此演算法与冒泡排序的不同處在於排序時是以双向在序列中進行排序。

伪代码[编辑]

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

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(list[i] > list[i + 1])  // test whether the two elements are in the correct order
            {
                swap(list[i], list[i + 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(list[i] < list[i - 1]) 
            {
                swap(list[i], list[i - 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 j, left = 0, right = len - 1;
	int temp;
	while (left < right) {
		for (j = left; j < right; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		right--;
		for (j = right; j > left; j--)
			if (arr[j - 1] > arr[j]) {
				temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
			}
		left++;
	}
}

C++实现[编辑]

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

JAVA实现[编辑]

	/**
	 * 鸡尾酒排序法
	 * 
	 * @param a
	 *            指定整型数组
	 */
	public void sort(int[] a) {
		//需要来回a,length/2趟
		for (int i = 0; i < a.length / 2; i++) {
			//类冒泡,交换最大值至右端
			for (int j = i; 1 + j < a.length - i; j++)
				if (a[j] > a[1 + j])
					Arr.swap(a, j, 1 + j);
			//类冒泡,交换最小值至左端
			for (int j = a.length - i - 1; j > i; j--)
				if (a[j - 1] > a[j])
					Arr.swap(a, j - 1, j);
		}
	}

複雜度[编辑]

鸡尾酒排序最糟或是平均所花費的次數都是O(n^2),但如果序列在一開始已經大部分排序過的話,會接近O(n)

額外連結[编辑]