2.cpp

算法代码

#include <string.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include<iostream> 

#define MAXNUM 1000                   //排序的元素个数    堆排序可以处理的最大个数为1024×63
#define MAXLEN 16                   //排序的元素长度（0到MAXLEN）

using namespace std;

typedef unsigned long int ULong; 

char s[63]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

void creat(char p[][MAXLEN])  //生成字符串
{   
    int i,j,k;

	cout<<"以下为创建数组的结果"<<endl;
	for(i=0;i<MAXNUM;i++)
	{
		k=rand()%16;
		for(j=0;j<k;j++)
		{
			p[i][j]=s[rand()%62];
			cout<<p[i][j];
		}
		p[i][j]='\0';
		cout<<endl;
	}
	cout<<endl;
}
void print(char p[][MAXLEN])
{
	int i,j;
	for(i=0;i<MAXNUM;i++)
	{
		
		for(j=0;p[i][j]!='\0';j++)
		{
			cout<<p[i][j];
		}
		cout<<endl;
	}
	cout<<endl;
}
/////////////////////////////////////////////////////////////////////////

ULong heapSize = 0; 

ULong Parent(ULong index) { 

//因为C语言的数组起始下标为0 
//所以和《算法导论》中的代码有点不同 
//index >> 1 == i / 2; 
return (index % 2) ? (index >> 1) : ((index >> 1) - 1); 

} 

ULong Left(ULong index) { 

//index << 1 == index * 2; 
return ((index << 1) + 1); 

} 

ULong Right(ULong index) { 

return ((index << 1) + 2); 

} 
void swap(char str[][MAXLEN],ULong i,ULong j) { 

strcpy(str[MAXNUM],str[i]);
strcpy(str[i],str[j]);
strcpy(str[j],str[MAXNUM]);

} 
//array[index] 与其左右子树进行递归对比 
//用最大值替换array[index] 
void maxHeapify(char str[][MAXLEN], ULong index) { 

ULong largest = 0; 
ULong left = Left(index); 
ULong right = Right(index); 

if ((left <= heapSize) && (strcmp(str[left],str[index])>0))
largest=left; 
else 
largest = index; 

if ((right <= heapSize) && (strcmp(str[right],str[largest])>0)) 
largest = right; 

if (largest != index)
{ 
	swap(str,index, largest); 
	maxHeapify(str, largest); 
} 

} 

//初始化堆，将数组中的每一个元素置放到适当的位置 
//完成之后，堆顶的元素为数组的最大值 
void buildMaxHeap(char str[][MAXLEN], ULong length) { 

int i; 
heapSize = length; 

for (i = (length >> 1); i >= 0; i--) 
maxHeapify(str, i); 

} 

void heapSort(char str[][MAXLEN], ULong length) { 

int i; 

buildMaxHeap(str, (length - 1)); 

//堆顶元素（即数组的最大值）被置换到数组的尾部 
//然后从堆中移除该元素 
//然后重建堆 
for (i = (length - 1); i >= 1; i--) { 
swap(str,0, i); 
heapSize--; 
maxHeapify(str, 0); 
} 

} 

/////////////////////////////////////////////////
void INSERTIONSORT(char str[][MAXLEN]) //插入排序
{
	int i,j;
	for(j=1;j<MAXNUM;j++)
	{
		strcpy(str[MAXNUM],str[j]);
		i=j-1;
		while(i>=0&&strcmp(str[i],str[MAXNUM])>0)
		{
			strcpy(str[i+1],str[i]);
			i--;
		}
		strcpy(str[i+1],str[MAXNUM]);
	}
}
///////////////////////////////////////////////////////////////////
void popo(char s1[][MAXLEN])
{
	int i,j,exchange;
	for (i=0;i<MAXNUM-2;i++)/*这里开始就是冒泡排序 */ 
	{ 
		exchange=0; 
		for(j=0;j<MAXNUM-2;j++) 
			if (strcmp(s1[j],s1[j+1])>0) 
			{ 
				strcpy(s1[MAXNUM],s1[j]); 
				strcpy(s1[j],s1[j+1]); 
				strcpy(s1[j+1],s1[MAXNUM]); 
				exchange=1; 
			} 
			if(!exchange) 
				break; 
	} 
}
///////////////////////////////////////////////////////////////////////
int PARTITION(char str[][MAXLEN],int low, int high) //自己另外学的算法
{
 strcpy(str[MAXNUM],str[low]);
 strcpy(str[MAXNUM+1],str[low]);
 while (low < high) 
 {
  while (low < high && strcmp(str[high],str[MAXNUM+1])>0) --high;
  strcpy(str[low],str[high]);
  while (low < high && !(strcmp(str[low],str[MAXNUM+1])>0)) ++low;
  strcpy(str[high],str[low]);
 }
    strcpy(str[low],str[MAXNUM]);
 return low;
}
/*
int PARTITION(char str[][MAXLEN],int p,int r)   //书上的PARTITION算法，运行的结果很不好。不但出现指针数组方面的错误，而且排序并不正确
{
	int x,i,j,k;
	strcpy(str[MAXNUM],str[r]);//x=maxnum
	//strcpy(str[MAXNUM+1],str[r]);//K=maxnum+1
	i=p-1;
	for(j=p;j<r-1;j++)
	{
		if(strcmp(str[MAXNUM],str[j])>0)
		{
			i=i+1;
			strcpy(str[MAXNUM+1],str[j]);
			strcpy(str[j],str[i]);
			strcpy(str[i],str[MAXNUM+1]);
		}
	}
	strcpy(str[MAXNUM+1],str[r]);
	strcpy(str[r],str[i+1]);
	strcpy(str[i+1],str[MAXNUM+1]);
	return i+1;
}*/
void QUICKSORT(char str[][MAXLEN],int p,int r)  //快速排序
{
	int q;
	if(p<r)
	{
		q=PARTITION(str,p,r);
		QUICKSORT(str,p,q-1);
		QUICKSORT(str,q+1,r);
	}
}
////////////////////////////////////////////////////////////////////////////////
/*
void merge(char str[][MAXLEN], int p, int q, int r)  
{  
	int s=q-p+1;  
	int t=r-q;
	int i;
	char L[MAXNUM][MAXLEN];  
	char R[MAXNUM][MAXLEN];  
	for(i=0;i<s;i++)strcpy(L[i],str[p+i]);
	for(i=0;i<t;i++) strcpy(R[i],str[q+i+1]);
	i=0;             // 不能重复定义　i 
	int j=0;  
	for(int k=p;k<=r;k++)  
	{  
		if(strcmp(R[j],L[i])>0) 
		{  
			if (i<s)                         // 检测R和L数组的边界 
			{    
				strcpy(str[k],L[i++]); 
			} 
			else 
			{ 
				strcpy(str[k],R[j++]); 
			} 
		}
		else   
		{    
			if (j  < t)                      // 检测R和L数组的边界 
			{ 
				strcpy(str[k],R[j++]); 
			} 
			else 
			{ 
				strcpy(str[k],L[i++]);  
			}  
		} 
	}   
	delete [] R;  
	delete [] L;  
}  

void merge_sort(char str[][MAXLEN],int lhs, int rhs)  
{  
	if(lhs  < rhs)
	{  
		int q=(lhs+rhs)/2;  
		merge_sort(str,lhs,q);  
		merge_sort(str,q+1,rhs);  
		merge(str,lhs,q,rhs);  
	} 
}  
*/
////////////////////////////////////////////////////////////////////////////////////
void main()
{   
	char str[MAXNUM+2][MAXLEN]; 

/*	creat(str);	
    merge_sort(str,0,MAXNUM);
	cout<<"归并排序结果"<<endl;
	print(str);	
*/
	creat(str);	
	heapSort(str, MAXNUM);
	cout<<"堆排序结果"<<endl;
	print(str);	

	creat(str);	
	QUICKSORT(str,0,MAXNUM);
	cout<<"快速排序结果"<<endl;
	print(str);	

	creat(str);
    popo(str);
	cout<<"冒泡排序结果"<<endl;
	print(str);	
	
	creat(str);
	INSERTIONSORT(str);
	cout<<"插入排序结果"<<endl;
	print(str);	


}