sort.cpp

冒泡

#include <iostream>
#include <fstream>
#include <iomanip>
#include <conio.h>
#include <ctime>
#include <string>
#include <stdio.h>

using namespace std;

#define MAXSIZE 11200

typedef struct
{
	int num[MAXSIZE+1];
	int length;
}SqList;


void LoadFileData(int number[], int &length, char *filename)
{
	int i;
	i=1;
	fstream indata(filename);
	while(indata>>number[i]){
		i++;
	}
	length=--i;
	indata.close();
}


void SaveSortData(int number[], int length, char *filename)
{
	fstream outdata(filename, ios::out);
	for(int i=1; i<length+1; i++)
	{
		outdata<<number[i]<<" ";
	}
	outdata.close();
}


void RandomNumber(int number[], int n, int max, bool flag)
{
	srand((unsigned)time(NULL));
	for(int i=1; i<n+1; i++)
	{
		number[i]=rand()%max;
	}
	if(flag)
	{
		SaveSortData(number, n, "temp.txt");
	}
}

void Display(int number[], int n)
{
	for(int i=1; i<=n; i++)
	{
		printf("%d ", number[i]);
	}
}


//各種排序算法在這裡

//冒泡
void BubbleSort(SqList &list, int &mov, int &cmp)
{
	bool flag=true;
	int temp;
	for (int j=1; j<list.length&&flag; j++)
	{
		flag=false;
		for(int i=1; i<=list.length-j; i++)
		{
			cmp++;
			if(list.num[i]>list.num[i+1])
			{
				temp=list.num[i];
				list.num[i]=list.num[i+1];
				list.num[i+1]=temp;
				mov++;
				flag=true;
			}
		}
	}
}

//堆
void HeapAdjust(int num[], int s, int m, int &mov, int &cmp)
{
	int j, rc;
	rc=num[s];
	mov++;

	for(j=s*2; j<=m; j*=2)
	{
		cmp+=2;
		if(j<m&&num[j]<num[j+1])
			j++;
		if(rc>num[j])
			break;
		num[s]=num[j];
		s=j;
		mov++;
	}

	num[s]=rc;
	mov++;
}

void HeapSort(SqList &list, int &mov, int &cmp)
{
	int i,temp;

	for(i=list.length/2; i>0; i--)
	{
		HeapAdjust(list.num, i, list.length, mov, cmp);
	}

	for(i=list.length; i>1; i--)
	{
		temp=list.num[1];
		list.num[1]=list.num[i];
		list.num[i]=temp;
		mov+=3;
		
		HeapAdjust(list.num,1,i-1,mov,cmp);
	}
}

//快速

int Partition(int data[], int low, int high, int &mov, int &cmp)
{
	int pivotkey;

	data[0]=data[low];
	pivotkey=data[low];
	mov+=2;

	while(low<high)
	{
		while(low<high&&data[high]>=pivotkey)
		{
			cmp++;
			high--;
		}
		data[low]=data[high];


		while(low<high&&data[low]<=pivotkey)
		{
			cmp++;
			low++;
		}
		data[high]=data[low];
		cmp+=2;
		mov+=2;
	}

	data[low]=data[0];
	mov++;
	return low;
}

void QkSort(int data[], int low, int high, int &mov, int &cmp)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(data, low, high, mov, cmp);
		QkSort(data, low, pivotloc-1, mov, cmp);
		QkSort(data, pivotloc+1, high, mov,cmp);
	}
}

void QuickSort(SqList &list, int &mov, int &cmp)
{
	QkSort(list.num, 1, list.length, mov, cmp);
}



//簡單選擇

void SelectSort(SqList &list, int &mov, int &cmp)
{
	int i=0, j=0;
	int min,temp;
	for(i=1; i<list.length; i++)
	{
		min=i;
		for(j=i+1; j<=list.length; j++)
		{
			cmp++;
			if(list.num[j]<list.num[min])
			{
				min=j;
			}
		}

		if(min!=i)
		{
			temp=list.num[i];
			list.num[i]=list.num[min];
			list.num[min]=temp;
			mov+=3;
		}
	}
}

//直接插入
void InsertSort(SqList &list, int &mov, int &cmp)
{
	for(int i=2; i<=list.length; i++)
	{
		cmp++;
		if(list.num[i]<list.num[i-1])
		{
			list.num[0]=list.num[i];
			list.num[i]=list.num[i-1];
			mov=mov+2;
			cmp++;

			for(int j=i-2; list.num[0]<list.num[j]; --j,cmp++,mov++)
			{
				list.num[j+1]=list.num[j];
			}

			list.num[j+1]=list.num[0];
			mov++;
		}
	}
}




void CompareDisplay(int mov, int cmp, string str)
{
	cout<<str;
	cout<<"Mov:"<<setw(10)<<mov;
	cout<<"\t\tcmp:"<<setw(10)<<cmp<<endl;
}

void Compare(SqList &list, int length)
{
	int mov=0, cmp=0;
	list.length=length;
	//排序算法引用寫在這裡
	
	LoadFileData(list.num, list.length, "temp.txt");
	BubbleSort(list, mov, cmp); 
	CompareDisplay(mov, cmp, "冒泡排序:  "); 
	SaveSortData(list.num, list.length, "BubbleSort.txt"); 
	
	mov=0; cmp=0;
	LoadFileData(list.num, list.length, "temp.txt");
	HeapSort(list, mov, cmp); 
	CompareDisplay(mov, cmp, "堆排序:  "); 
	SaveSortData(list.num, list.length, "HeapSort.txt"); 

	mov=0; cmp=0;
	LoadFileData(list.num, list.length, "temp.txt");
	QuickSort(list, mov, cmp); 
	CompareDisplay(mov, cmp, "快速排序:  "); 
	SaveSortData(list.num, list.length, "QuickSort.txt"); 
	
	mov=0; cmp=0;
	LoadFileData(list.num, list.length, "temp.txt");
	SelectSort(list, mov, cmp); 
	CompareDisplay(mov, cmp, "选择排序:  "); 
	SaveSortData(list.num, list.length, "SelectSort.txt"); 

	mov=0; cmp=0;
	LoadFileData(list.num, list.length, "temp.txt");
	InsertSort(list, mov, cmp); 
	CompareDisplay(mov, cmp, "插入排序:  "); 
	SaveSortData(list.num, list.length, "InsertSort.txt"); 


	
	
	printf("all sort\n");
}


void MainMenu(SqList &list, int mov, int cmp, int &length)
{
	printf("\n\t1.随机生成数\n");
	printf("\t2.所有排序\n");
	printf("\t0.离开\n");
	int select=0;
	scanf("%d",&select);
	switch(select)
	{
	case 1: 
		printf("输入个数:\n");
		scanf("%d",&length);
		RandomNumber(list.num, length, 1000, true);
		list.length=length;
		Display(list.num, list.length);
		break;
	case 2:
		Compare(list, length);
		break;
	case 0:
		exit(0);
	}
	LoadFileData(list.num, list.length, "temp.txt");
}


int main()
{
	SqList list;
	int length=0;

	while(true)
	{
		MainMenu(list, 0, 0, length);
	}
	getch();
	return 0;
}