本文概述
- 复杂
- C程序
- C ++程序
- Java程序
- C＃程序
- Python程序
- 休息计划
- JavaScript程序
算法
在鸡尾酒式排序中, 一个迭代包括两个阶段：
- 第一阶段像从左到右的气泡排序那样遍历整个数组。比较相邻元素, 如果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 swapA={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) |
#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 mutbegin = 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推荐阅读
- 梳排序算法实现
- 数据结构（循环单链接列表）
- 数据结构（循环队列）
- 数据结构（循环双链表）
- 桶排序算法实现
- 冒泡排序算法实现全解
- 图遍历算法（广度优先搜索算法）
- 比并排序算法实现详解
- B树实现详细步骤解析