c++鸡尾酒排序（优化）

• 鸡尾酒排序（优化）
• 前言
• 一、鸡尾酒排序是什么？
• 二、程序实现步骤
• • 1.引入库
  • 2.子函数1（输出函数）
  • 子函数2（鸡尾酒排序）
  • 主函数
  • 输出结果
  • • 数学解释
• 三、总结
• • • 改进方案

作为刚刚入门c和c++的小菜鸡，心血来潮决定写点学习笔记，希望大家提出改进意见。

鸡尾酒排序是冒泡排序的优化版本，使原来的正向排序改为包含从前到后和从后到前的排序方式（双向冒泡）。

代码如下（示例）：

#include 
#include //随机函数
#include //测试时间
#include //构造均态分布和正态分布的数组
using namespace std;

如需添加随机函数构建数组可加后三个头文件

代码如下：

void Show(const int *a, int n)
{
	if(n<=0) return;
	cout << a[0];
	for(int i=1; i 
子函数2（鸡尾酒排序） 
代码如下（示例）：
 
void CocktailSort(int *a, int n)
{
	for(int i=0; i a[j+1])
				{
					swap(a[j], a[j+1]);
					flag = 0;
				}
				Show(a, n, j);
			}
		}
		else
		{
			cout << "n第" << i+1 << "轮(从右到左)" << endl;
			for(int j=n-1-i/2; j>i/2; j--)
			{
				if(a[j-1] > a[j])
				{
					swap(a[j-1], a[j]);
					flag = 0;
				}
				Show(a, n, j-1);
			}
		}
		cout << "本轮" << (flag? "无" : "有") << "交换" << endl;
		if(flag)
			break;
	}
}
 
主函数 
代码如下（示例）：
 
int main()
{
	int a[] = {8, 1, 0, 9, 7, 5};//嘿嘿嘿，整个活
	int n = sizeof(a)/sizeof(*a);
	
	cout << "原始数据: ";
	Show(a, n);
	
	CocktailSort(a, n);
	
	cout << "n鸡尾酒排序结果: ";
	Show(a, n);
	
	return 0;
}
 
输出结果 
数学解释 
第一轮i=0,j=0,j<5 (n-1- ( i/2) =6-1-0=5)
 第二轮i=1,j=5(n-1- (i/2) ),j>0( i/2=0/2=1)
 以下同理。
 
三、总结 
我将传统鸡尾酒中的内循环j取值和范围做了调整（使用i/2），使遍历次数减少，同时此程序将交换情况清晰展示。
 
改进方案 
加入index变量，每一轮记录最后发生交换的下标（分left，right两行记录），判断循环继续条件为（left=right时结束循环，可以省下原程序中最后一轮无交换情况。