1.鸡尾酒（双向冒泡）排序简介
鸡尾酒排序也就是“定向冒泡排序”、“双向冒泡排序”和“改进冒泡排序”, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
2.鸡尾酒（双向冒泡）排序基本原理
使用鸡尾酒排序为一列数字进行排序的过程可以通过右图形象的展示出来：
数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
算法原理：数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
3.鸡尾酒（双向冒泡）排序算法基本过程
（1）先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端；
（2）再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端；
以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束.
4.鸡尾酒（双向冒泡）排序算法分析
（1）时间复杂度：鸡尾酒排序的效率还是很低的，两层循环，时间复杂度为 O(n^2) 。
（2）空间复杂度：由于只需要几个临时变量，所以空间复杂度为 O(1) 。
那么何以见得鸡尾酒排序比冒泡排序好一点呢？
考虑这样的一个序列：(2,3,4,5,1) 。如果使用鸡尾酒排序，一个来回就可以搞定；而冒泡排序则需要跑四趟。
其根本原因在于冒泡是单向的，如果从左向右冒泡，对于小数靠后就会很不利（一趟只能挪一个位置，那就需要多次循环。这种数又被称之为乌龟）；相应的，如果从右向左冒泡，对于大数靠前又会很不利（靠前的一只大乌龟）。鸡尾酒排序的优点就在于这里，由于在序列中左右摇摆（为此鸡尾酒排序又称之为 shaker sort），两种较差的局面就能得到规避，以此在性能上带来一些提升。
5.鸡尾酒（双向冒泡）排序算法C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <stdio.h> #include <stdlib.h> #include <math.h> #define N 15 // 鸡尾酒（双向冒泡）排序算法 void Cocktail_Sort(int *data, int n) { int i = 0, max_k = 0, min_k= 0, t = 0, temp = 0; int min = 0, max = 0; int min_pos = 0, max_pos = n - 1; min = max = data[0]; while(t < n / 2)//趟数（这里一趟指的是一个来回） { t++; for (i = min_pos; i <= max_pos; i++) { if (data[i] > max) { max = data[i];//记录最大值的值和位置 max_k = i; } } //将末尾数与最大值位置交换（末尾是相对的哈） temp = data[max_pos]; data[max_pos] = data[max_k]; data[max_k] = temp; max_k = --max_pos; max = data[max_pos]; for (i = max_pos; i >= min_pos; i--) { if (data[i] < min) { min = data[i];//记录最小值的值和位置 min_k = i; } } //将首位数与最小值位置交换（首位也是相对的哈） temp = data[min_pos]; data[min_pos] = data[min_k]; data[min_k] = temp; min_k = ++min_pos; min = data[min_pos]; } } //打印输出数组 void Cocktail_Show(int *data, int n) { int i = 0; for (i = 0; i < n - 1; i++) { printf("%d ", data[i]); } printf("%d\n", data[i]); } int main() { int i = 0; int data[N] = {0}; srand((unsigned int)NULL); for (i = 0; i < N; i++) { data[i] = rand() % 50 + rand() % 50; } Cocktail_Show(data, N); Cocktail_Sort(data, N); Cocktail_Show(data, N); return 0; } |
6.鸡尾酒（双向冒泡）排序算法C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <iostream> using namespace std; //鸡尾酒排序--双向冒泡排序（改进的冒泡排序） void CocktailSort(int *a,int nsize) { int tail=nsize-1; for (int i=0;i<tail;) { for (int j=tail;j>i;--j) //第一轮，先将最小的数据排到前面 { if (a[j]<a[j-1]) { int temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } ++i; //原来i处数据已排好序，加1 for (j=i;j<tail;++j) //第二轮，将最大的数据排到后面 { if (a[j]>a[j+1]) { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } tail--; //原tail处数据也已排好序，将其减1 } } void OutPut(int *b,int nLength) { for (int i=0;i<nLength;i++) { cout<<b[i]<<'\t'; } cout<<endl; } int main() { int nData[]={1,4,2,5,67,86,24,63,676,23,1,3,2,34}; CocktailSort(nData,sizeof(nData)/sizeof(nData[0])); OutPut(nData,sizeof(nData)/sizeof(nData[0])); return 1; } |
