雞尾酒排序算法是一種定向的冒泡排序算法峡捡，由于其來(lái)回折騰，因此又叫雞尾酒攪拌排序诀浪、來(lái)回排序或者是漣漪排序棋返、快樂(lè)小時(shí)排序。這個(gè)算法與冒泡排序的不同之處在于排序時(shí)是以雙向在序列中進(jìn)行排序的雷猪。
算法思想：
- 采用冒泡排序的思路睛竣，第一躺沿正方向找到最大值；
- 第二趟求摇，從n-1個(gè)元素位置射沟，沿反方向找到最小值
- 第三趟殊者，從第2個(gè)元素位置，沿正方向找到第二大的值验夯，冒泡到n-1
- 重復(fù)上面的操作猖吴，直到排序完成
代碼實(shí)現(xiàn)
void cocktail_sort(int arr[], int len) {
int i, left = 0, right = len;
int temp;
while (left < right) {
for (i = left; i < right; i++)
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
right--;
for (i = right; i > left; i--)
if (arr[i - 1] > arr[i]) {
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
left++;
}
}
算法分析
- 最優(yōu)的情況下，復(fù)雜度為O(n)挥转，當(dāng)然海蔽，也是要引入標(biāo)志位
- 最差的情況下，復(fù)雜度為O(n^2)绑谣，當(dāng)然党窜，會(huì)比冒泡排序算法性能好一點(diǎn)
- 平均復(fù)雜度為O(n^2)
- 相比于冒泡排序，不同的地方在于從低到高借宵，然后從高到低幌衣，因此可以得到比冒泡排序稍微好一些的性能。
可以這么總結(jié)：相對(duì)于冒泡排序壤玫，采用雞尾酒排序豁护，性能至少不會(huì)變壞，大多數(shù)情況下能獲得更好的性能欲间。
過(guò)程舉例
cocktail_sort_example.png
動(dòng)態(tài)過(guò)程
Sorting_shaker_sort_anim.gif
