#include<iostream>   //输入输出流预处理命令，相当于#include<stdio.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
void Bubble_sort(int a[], int n);
void Bubble_sort1(int a[],int n);
void dataGen1(int a[], int n);
void dataGen2(int a[], int n);
void dataGen3(int a[], int n);
void dataGen4(int a[], int n);

int main()
{
	int a[10000], step = 1000;
	clock_t start1, finish1, start2, finish2;
	for(int n = 1000; n <= 10000; n += step){
        dataGen4(a, n);    //初始化数据a[],可以给出其它数据
		start1 = clock();
		Bubble_sort(a, n);
		finish1 = clock();
        dataGen4(a, n);     //重新初始化数据a[]
		start2 = clock();
		Bubble_sort1(a, n);
		finish2 = clock();
		cout << n << ' ' << (finish1-start1)    //相当于printf("d%  d%  d%\n",
			<< ' ' << (finish2-start2)<< endl;  // n, finish1-start1, finish2-start2);
	}
	return 0;
}
void Bubble_sort(int a[], int n)
{
	for(int j = n-1; j >= 1; --j){
		for(int k =0; k < j; ++k)
			if (a[k] > a[k+1]){
				int b;
				b = a[k];
				a[k] = a[k+1];
				a[k+1]=b;
			}
	}
}
void Bubble_sort1(int a[],int n)             //改进的起泡排序
{ 
	bool change = true;
	for(int i=n-1; ( i >= 1 ) && change; --i ) {
	change = false;
	for(int j=0;j<i;++j)
		if(a[j]>a[j+1]){
			int k=a[j];
			a[j]=a[j+1];
			a[j+1]=k;
			change = true;
		}
	}
}

void dataGen1(int a[], int n)
{
	for(int i = 0; i < n; i++)
		a[i] = rand() %  n;
}

void dataGen2(int a[], int n)
{
	for(int i = 0; i < n; i++)
		a[i] = n - i;
}

void dataGen3(int a[], int n)
{
	for(int i = 0; i < n; i++)
		a[i] = i + 100;
}

void dataGen4(int a[], int n)
{
	for(int i = 0; i < n / 2; i++)
		a[i] = i;
	for(int j = n / 2; j < n; j++)
		a[j] = n - j;
}