17_2_2.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include <stdlib.h>
#define MAX_SIZE 100

void Swap(int &a, int &b)
{
	int t	= a;
	a		= b;
	b		= t;
}

void Print(int a[], int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}

void main()
{
	cout << "***************** 双向起泡排序 **********************" << endl;
	cout << endl;
	cout << "请输入要排序的数据，输入#结束：" << endl;
	
	// 输入

	int a[MAX_SIZE];
	int i = 0;
	char c[8];
	while (c[0] != '#')
	{
		cin >> c;
		if (c[0] != '#')
			a[i] = atoi(c);
		i++;
	}
	int n			= i - 1;

	// 统计模式的开关
	bool sta = 0;
	if (sta)
	{
		for (int i = 0; i < 100; i++)
		{
			a[i] = 100 - i;
		}
		n = 100;
	}

	bool changed	= true;
	int max			= n - 1;
	int min			= 0;
	int nextMax		= n - 1;
	int nextMin		= 0;
	//  统计
	int cpr			= 0;
	int run			= 0;
	//  end统计
	int j;
	while (changed)
	{
		changed = false;
		for (i = min; i < max; i++)
			if (a[i] > a[i + 1])
			{
				changed = true;
				Swap(a[i], a[i + 1]);
				nextMax = i;
				cpr++;
				run += 5;
			}
		for (j = max; j > min; j--)
			if (a[j - 1] > a[j])
			{
				changed = true;
				Swap(a[j], a[j - 1]);
				nextMin = j;
				cpr++;
				run += 5;
			}
		max = nextMax;
		min = nextMin;
		run += 2;
	}

	cout << "排序后的数据为：	" << endl;
	Print(a, n);
	cout << "比较次数为：		" << cpr << endl;
	cout << "运行次数为：		" << run << endl;
}