2019-06-26 244 views 评论

鸡尾酒排序问题

题目解释

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

第一趟是正向排序，选出第n个值（最大值）；
第二趟是反向排序，选出第1个值（最小值）；
第三趟是正向排序，选出第n-1个值（次大值）；
第四趟是反向排序，先出第2个值（次小值）。

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

代码实现

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

}