srcmini本文概述
鸡尾酒排序是冒泡排序的一种变体, 它交替在两个方向上遍历列表。它与冒泡排序的不同之处在于, 冒泡排序仅在向前方向遍历列表, 而此算法在一次迭代中既向前又向后遍历。
算法
在鸡尾酒式排序中, 一个迭代包括两个阶段：
- 第一阶段像从左到右的气泡排序那样遍历整个数组。比较相邻元素, 如果left元素大于right元素, 则我们交换这些元素。列表中最大的元素位于正向传递中的数组末尾。
- 第二阶段从最右边的未排序元素到左边遍历数组。比较相邻元素, 如果right元素小于left元素, 则交换这些元素。列表中最小的元素在向后传递时位于数组的开头。
该过程继续进行, 直到列表未排序为止。
例
考虑数组A：{8, 2, 3, 1, 9}。使用Cocktail sort对数组的元素进行排序。
迭代1：
前传：
compare 8 with 2; 8>2 → swap(8, 2)
A={2, 8, 3, 1, 9}
Compare 8 with 3; 8>3 → swap(8, 3)
A={2, 3, 8, 1, 9}
Compare 8 with 1; 8 > 1 → swap(8, 1)
A = {2, 3, 1, 8, 9}
Compare 8 with 9; 8<9 → do not swap在第一遍通过的末尾：列表的最大元素位于末尾。
A={2, 3, 1, 8, 9 }后退通行证：
compare 8 with 1; 8> 1 → do not swap
A={2, 3, 1, 8, 9 }
compare 1 with 3 ; 3>1 → swap(1, 3)
A={2, 1, 3, 8, 9 }
compare 1 with 2 ; 2> 1 → swap(1, 2)
A={1, 2, 3, 8, 9}在第一个后退通道结束时；最小的元素已放置在数组的第一个索引处。
如果我们看一下第一步产生的清单；我们可以发现列表已经按照升序排序, 但是算法会完全处理自身。
复杂
| 复杂 | 最好的情况 | 平均情况 | 最差的情况 |
|---|---|---|---|
| 时间复杂度 | O(n2) | O(n2) | O(n2) |
| Space Complexity | O(1) |
C程序
#include <stdio.h>
int temp;
void Cocktail(int a[], int n)
{
int is_swapped = 1;
int begin = 0, i;
int end = n - 1;
while (is_swapped) {
is_swapped = 0;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
if (!is_swapped)
break;
is_swapped = 0;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
++begin;
}
}
int main()
{
int arr[] = {0, 10, 2, 8, 23, 1, 3, 45}, i;
int n = sizeof(arr) / sizeof(arr[0]);
Cocktail(arr, n);
printf("printing sorted array :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}输出：
printing sorted array :
0 1 2 3 8 10 23 45C ++程序
#include <iostream>
using namespace std;
int temp;
void Cocktail(int a[], int n)
{
int is_swapped = 1;
int begin = 0, i;
int end = n - 1;
while (is_swapped) {
is_swapped = 0;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
if (!is_swapped)
break;
is_swapped = 0;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
++begin;
}
}
int main()
{
int arr[] = {0, 10, 2, 8, 23, 1, 3, 45}, i;
int n = sizeof(arr) / sizeof(arr[0]);
Cocktail(arr, n);
cout <<"printing sorted array :\n";
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<"\n";
return 0;
}输出：
printing sorted array :
0 1 2 3 8 10 23 45Java程序
public class CocktailSort
{
static int temp;
static void Cocktail(int a[], int n)
{
boolean is_swapped = true;
int begin = 0, i;
int end = n - 1;
while (is_swapped) {
is_swapped = false;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
if (!is_swapped)
break;
is_swapped = false;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
++begin;
}
}
public static void main(String[] args) {
int arr[] = {0, 10, 2, 8, 23, 1, 3, 45}, i;
int n = arr.length;
Cocktail(arr, n);
System.out.println("printing sorted array :\n");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}输出：
printing sorted array :
0 1 2 3 8 10 23 45C＃程序
using System;
public class CocktailSort
{
static int temp;
static void Cocktail(int[] a, int n)
{
Boolean is_swapped = true;
int begin = 0, i;
int end = n - 1;
while (is_swapped) {
is_swapped = false;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
if (!is_swapped)
break;
is_swapped = false;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
++begin;
}
}
public void Main() {
int[] arr = {0, 10, 2, 8, 23, 1, 3, 45};
int n = arr.Length, i;
Cocktail(arr, n);
Console.WriteLine("printing sorted array :\n");
for (i = 0; i < n; i++)
Console.Write(arr[i]+" ");
}输出：
printing sorted array :
0 1 2 3 8 10 23 45Python程序
def Cocktail(a, n):
is_swapped = True;
begin = 0
end = n - 1;
while is_swapped:
is_swapped = False;
for i in range(begin, end):
if a[i] > a[i + 1]:
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = True;
if not(is_swapped):
break;
is_swapped = False;
for i in range(end-1, begin-1, -1):
if a[i] > a[i + 1]:
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = True;
++begin;
arr = [0, 10, 2, 8, 23, 1, 3, 45];
n = len(arr);
Cocktail(arr, n);
print("printing sorted array :\n");
for i in range(0, n):
print(arr[i]), 输出：
printing sorted array :
0 1 2 3 8 10 23 45休息计划
fn main()
{
let mut a :[i32;8] = [0, 10, 2, 8, 23, 1, 3, 45];
let mut is_swapped = true;
let mut begin = 0;
let end = 7;
while is_swapped {
is_swapped = false;
for i in begin..end {
if a[i] > a[i + 1] {
let mut temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = true;
}
}
if !is_swapped
{
break;
}
is_swapped = false;
for i in (begin..(end-1)).rev()
{
if a[i] > a[i + 1]
{
let mut temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped =true;
}
}
begin=begin+1;
}
print!("printing sorted array :\n");
for i in 0..7
{
print!("{}", a[i]);
}
}输出：
printing sorted array :
0 1 2 3 8 10 23 45JavaScript程序
<html>
<head>
<title>Cocktail Sort</title>
</head>
<body>
<script>
function Cocktail( a, n)
{
var temp=0;
var is_swapped = 1;
var begin = 0;
var end = n - 1;
while (is_swapped) {
is_swapped = 0;
for (i = begin; i < end; ++i) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
if (!is_swapped)
break;
is_swapped = 0;
for (i = end - 1; i >= begin; --i) {
if (a[i] > a[i + 1])
{
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
is_swapped = 1;
}
}
begin=begin+1;
}
}
var txt = "<br>";
var arr = [0, 10, 2, 8, 23, 1, 3, 45];
var n = arr.length;
Cocktail(arr, n);
document.writeln("printing sorted array :\n"+txt);
for (i = 0; i < n; i++)
{
document.writeln(arr[i]+"/xa0");
}
</script>
</body>
</html>输出：
printing sorted array :
0
1 2 3 8 10 23 45
评论前必须登录！
注册