logo头像

不忘初心,奋力前行

鸡尾酒排序问题

本文于321天之前发表,文中内容可能已经过时,如有问题,请联系我。

题目解释

鸡尾酒排序问题实际上是冒泡排序的一个改进。冒泡排序是一个单向的递增或者递减的交换排序,而鸡尾酒排序则是双向的,也就是说,如果我们以要求一个数组有n个数字从小到大排序,则:

  • 第一趟是正向排序,选出第n个值(最大值);
  • 第二趟是反向排序,选出第1个值(最小值);
  • 第三趟是正向排序,选出第n-1个值(次大值);
  • 第四趟是反向排序,先出第2个值(次小值)。

然后以此类推,最后得出整个序列,所以实际上就相当于将原来的冒泡排序有一段代码写成了两段。然后为了优化运行时间,所以设置一个标志位,当确定没有元素交换的时候,就自动停止运行输出结果。

代码实现

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
void Cocktail(vector<int>& nums)
{
bool flag = false;
int cishu = 1;//输出需要而已
do
{
flag = false;
//正着走
for (int i = 0; i < nums.size() - 1; i++)
{
if (nums[i] > nums[i + 1])
{
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
flag = true;
}
}
//输出第cishu次排序的结果,正式使用去掉这部分
cout << "第" << cishu << "次排序结果为:";
showNums(nums);
++cishu;
//展示结束
flag = false;、
//反过来走
for (int j = nums.size() - 1; j > 0; j--)
{
if (nums[j] < nums[j - 1])
{
int tmp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = tmp;
flag = true;
}
}
//输出第cishu次排序的结果,正式使用去掉这部分
cout << "第" << cishu << "次排序结果为:";
showNums(nums);
++cishu;
//展示结
} while (flag);

}

代码测试

当我们输入的数组为9,5,7,4,2,1,8,12,33,21,3时,输出结果为

de285197fc948bae7c46d7e1017173d0.png

支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!