雞尾酒排序
@(F1 - 算法學習)[排序|noteton]
WIKI上的定義
雞尾酒排序，也就是定向冒泡排序、雞尾酒攪拌排序红氯、攪拌排序（也可以視作選擇排序的一種排序）框咙、漣漪排序、來回排序或者快樂小時排序痢甘，是冒泡排序的一種變形喇嘱。與冒泡排序的不同處在于排序時是以雙向在序列中進行排序。
Sorting_shaker_sort_anim.gif
| 分類 | 排序算法 |
|---|---|
| 數(shù)據(jù)結(jié)構 | 數(shù)組 |
| 最差時間復雜度 | |
| 最優(yōu)時間復雜度 | |
| 平均時間復雜度 |
與冒泡排序不同的地方
雞尾酒排序等于是冒泡排序的輕微變形塞栅。不同的地方在于從低到高然后從高到低（有先后順序婉称，并非同時；大循環(huán)下第一個循環(huán)是從開始掃到結(jié)束构蹬，將最大的歸到最后王暗；第二個循環(huán)是從倒數(shù)第二個位置往開始端掃，將最小的歸到開始的位置）庄敛，而冒泡排序則僅僅從低到高去比較序列里的每個元素俗壹。他可以得到比冒泡排序稍微好一點的效能，原因是冒泡排序只從一個方向進行比對（由低到高）藻烤，每次只移動一個項目和绷雏。
以排序（2,3,4,5,1）為例，雞尾酒排序只要訪問一次序列就可以完成排序怖亭，但如果使用冒泡排序需要四次涎显。但是在亂數(shù)序列的狀態(tài)下，雞尾酒排序和冒泡排序的效率都很差兴猩。
偽代碼
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;
}
}
Java實現(xiàn)
/**
* 雞尾酒排序法
*
* @param a
* 指定整型數(shù)組
*/
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);
}
}
注意看這里的代碼實現(xiàn)倾芝，沒有了狀態(tài)變量sorted讨勤，最外面的while循環(huán)也被替代成確定length/2趟的for循環(huán)，因為循環(huán)內(nèi)有兩個for各分擔餓了一般的工作晨另，所以潭千，大循環(huán)只需要進行一半。這個在代碼的具體實現(xiàn)時看具體情況吧借尿，如果分析不清楚刨晴，就用偽代碼中的設置狀態(tài)變量也未嘗不可。PS路翻，偽代碼要像思維導圖一樣逼著自己先寫著狈癞！
C實現(xiàn)
#include<stdio.h>
#include<stdbool.h>
void swap(int *a ,int *b);
int main()
{
int a[] = {4,3,1,6,5,7,2,9,8};
bool sorted = true;
int length = sizeof(a) / sizeof(a[0]);
int top = length - 1;
int bottom = 0;
int tmp = 0;
while (sorted)
{
sorted = false;
for (int i = bottom; i < top; i++)
{
if (a[i]<a[i - 1])
{
swap(&a[i], &a[i - 1]);
/*
{
tmp=a[i];
a[i] = a[i - 1];
a[i - 1] = tmp;
}
*/
sorted = true;
}
}
top--;
for ( int i = top; i >bottom; i--)
{
if (a[i]>a[i + 1])
{
swap(&a[i], &a[i + 1]);
/*
{
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
}
*/
sorted = true;
}
}
bottom++;
}
for (int i = 0; i < length; i++)
{
printf("%d", a[i]);
}
}
void swap(int *a, int *b)
{
int tmp = 0;
tmp = *a;
*a = *b;
*b = tmp;
}
