efficience.cpp

多种排序算法（冒泡排序

#include<iostream>
#include<stdio.h>
#include"malloc.h" /* malloc()等 */ 
#include"process.h" /* exit() */ 
#include <time.h> 
#define MAX_NODE 10
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * (i) + 2)
#include<String.h>
#include<iomanip.h>
#include<iostream.h> 
#define M 11 
typedef int ElemType; 

typedef char *KeyType;

int mov;
int cmp;
typedef struct /*静态查找表的顺序存储结构 */ 
{ 
ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */ 
int length; /* 表长度 */ 
}SSTable; 

void Creat(SSTable *ST,int n,int b[]) 
{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */ 
	int i; 
	(*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */ 
	if(!(*ST).elem) 
		{printf("ERROR\n");exit(0);} /*内存分配失败结束程序*/ 
	for(i=1;i<=n;i++) 
	{ 
	
		*((*ST).elem+i)=b[i]; /* 依次赋值给ST */ 
	} 
	(*ST).length=n; 
}

/*堆排序*/


void max_heapify(int A[], int i, int heap_size)
{
        int l, r, largest;
        int tmp;
        l = LEFT(i);
        r = RIGHT(i);
        if (l < heap_size && A[l] > A[i])
		{
			largest = l;
		     cmp++;
		}
        else
            largest = i;
        if (r < heap_size && A[r] > A[largest])
		{
			largest = r;
		    cmp++;
		}

        if (largest != i)
        {
            tmp = A[i];
            A[i] = A[largest];
            A[largest] = tmp;
			mov=mov+3;
            max_heapify(A, largest, heap_size);
        }
}
void build_max_heap(int A[], int heap_size)
{
        int i;
        for (i = (heap_size / 2) - 1; i >= 0; i--)
        {
            max_heapify(A, i, heap_size);
        }
}
void heapsort(int A[], int heap_size)
{
        int i;
        int tmp;
        build_max_heap(A, heap_size);
        for (i = heap_size - 1; i >= 1; i--)
        {
            tmp = A[i];
            A[i] = A[0];
            A[0] = tmp;
            heap_size--;
            max_heapify(A, 0, heap_size);
        }
}
void GoHeapSort(int arry[],int n) 
{      mov=0;
       cmp=0;
        int i; 
        int heap_size =n;
        int heap[1000];
       
        for(i = 0; i < heap_size; i++)
        {
           heap[i] = arry[i+1];  
         
        }
        
        heapsort(heap, heap_size);
		printf("  堆排序的: ");
        //for (i = 0; i < heap_size; i++)
       // {
       //     printf("%d ", heap[i]);
       // }
         printf("比较次数： ");
		printf("%d      ",cmp);
		printf("移动次数： ");
		printf("%d      ",mov);
        printf("\n");
} 







/*归并排序*/

struct rec 
{ 
int key;
int data; 
}; 
typedef rec sqlist[1000]; 
//void output( sqlist r, int n ) 
//{ 
//for ( int i = 0; i < n; i++ ) 
//{ 
//cout << setw( 4 ) << r[i].key; 
//} 
//cout << endl; 
//} 
void xuanze( sqlist b, int m, int n ) 
{ 
int i, j, k; 
for ( i = m; i < n - 1; i++ ) 
{ 
k = i; 
for ( j = i; j < n; j++ ) 
{ 
if ( b[k].key > b[j].key ) 
{ 
k = j; 
cmp++;
} 
cmp++;
} 
if ( k != i ) 
{ 
rec temp = b[k]; 
b[k] = b[i];b[i] = temp;
mov=mov+3; 
} 
} 
} 
void merge( sqlist r, int l, int m, int h, sqlist r2 ) 
{ 
xuanze( r, l, m ); 
xuanze( r, m, h ); 

int i, j, k; 
k = i = l; 
for ( j = m; i < m && j < h; k++ ) 
{ 
if ( r[i].key <= r[j].key ) 
{ 
r2[k] = r[i];i++; cmp++;mov++;
} 
else 
{ 
r2[k] = r[j];j++;  cmp++;mov++;
} 

} 
while ( j < h ) 
{ 
r2[k] = r[j];j++;k++; mov++;
} 
while ( i <= m ) 
{ 
r2[k] = r[i];i++;k++; mov++;
} 

} 
void GoMerge(int arry[],int n) 
{ 
//cout << "guibingfa2.cpp运行结果:\n"; 
sqlist a, b;int i, j = 0, k = n / 2; 
mov=0;
cmp=0;
for ( i = 1; i <= n; i++ ) 
{ 
a[i-1].key = arry[i];b[i-1].key = 0; 
} 
//cout << "排序前数组:\n"; 
//output( a, M ); 
//cout << "数组排序的过程演示:\n"; 
merge( a, j, k, n, b ); 
printf( "归并排序的: "); 
//output( b, n);
//for ( i = 0; i < n; i++ ) 
//{ 
//printf("%d ",b[i]);
//} 
//printf("\n");
       printf("比较次数： ");
		printf("%d      ",cmp);
		printf("移动次数： ");
		printf("%d      ",mov);
		printf("\n");

} 




/*冒泡排序*/
void BubbleSort(SSTable &ST){
	int i,j,n;
	for(i=1;i<ST.length;i++){
		for(j=1;j<ST.length;j++)
			if(ST.elem[j+1]<ST.elem[j]){
				cmp++;
				ST.elem[0]=ST.elem[j];
				ST.elem[j]=ST.elem[j+1];
				ST.elem[j+1]=ST.elem[0];
				mov=mov+3;
			}
	            cmp++;
	}
     printf("冒泡排序的: ");
	 //for(n=1;n<=ST.length;n++)
	//	printf("%d ",ST.elem[n]);
	    printf("比较次数： ");
		printf("%d      ",cmp);
		printf("移动次数： ");
		printf("%d      ",mov);
		printf("\n");
	
}

void BubSort(int n,int arry[]){
	SSTable ST;
    cmp=0;
	mov=0;
	Creat(&ST,n,arry);
	BubbleSort(ST);

}






/*折半插入排序*/

void BInsertSort(SSTable &ST){
	int i,j,n;
	int low,high,mid;
	for(i=2;i<=ST.length;++i){
		ST.elem[0]=ST.elem[i];
		   mov++;
		low=1;high=i-1;
		while(low<=high){
			mid=(low+high)/2;
			cmp++;
			if(ST.elem[0]<ST.elem[mid])
				high=mid-1;
			else low=mid+1;

		}
		for(j=i-1;j>=high+1;--j)
			ST.elem[j+1]=ST.elem[j];
		       mov++;
		ST.elem[high+1]=ST.elem[0];
		   mov++;
	}
	
	
	
}

void BinaryInsSort(int n,int arry[]){
    mov=0;
	cmp=0;
	SSTable ST;
	Creat(&ST,n,arry);
	BInsertSort(ST);
	printf("折半排序的: ");
	//	for(n=1;n<=ST.length;n++)
	//	printf("%d ",ST.elem[n]);
		printf("比较次数： ");
		printf("%d      ",cmp);
		printf("移动次数： ");
		printf("%d      ",mov);
		printf("\n");
}





/*简单选择排序*/
//void Creat(SSTable *ST,int n) 
//{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */ 
//	int i,temp; 
//	(*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */ 
//	if(!(*ST).elem) 
//		{printf("ERROR\n");exit(0);} /*内存分配失败结束程序*/ 
//	for(i=1;i<=n;i++) 
//	{ 
//		scanf("%d",&temp); 
//		*((*ST).elem+i)=temp; /* 依次赋值给ST */ 
//	} 
//	(*ST).length=n; 
//}

int SelectMinKey(SSTable &ST,int i){
	int n,m;
	m=i;
	for(n=i;n<ST.length;n++){
		if(ST.elem[n+1]<ST.elem[m]){
			m=n+1;
			cmp++;
		}
		cmp++;
	}
	return m;
	//printf("%d",ST.elem[0]);
}

void SelectSort(SSTable &ST){
	int i,j,n;
	for(i=1;i<ST.length;i++){
		j=SelectMinKey(ST,i);
		//if(i!=j)
			ST.elem[0]=ST.elem[i];
			ST.elem[i]=ST.elem[j];
			ST.elem[j]=ST.elem[0];
	        mov=mov+3;
	}
		printf("简单排序的: ");
	//	for(n=1;n<=ST.length;n++)
		//	printf("%d ",ST.elem[n]);
            printf("比较次数： ");
	     	printf("%d      ",cmp);
		    printf("移动次数： ");
		    printf("%d      ",mov);
		    printf("\n");
	
}

void SimpleSSort(int n,int arry[]){
	SSTable ST;
    cmp=0;
	mov=0;
	Creat(&ST,n,arry);
	SelectSort(ST);
	//SelectMinKey(ST,1);
}







/*快速排序*/


int Partition(SSTable &ST,int low,int high){

	ST.elem[0]=ST.elem[low];
	while(low<high){
		
		while(low<high&&ST.elem[high]>=ST.elem[0])
		{  
			--high;
		    cmp++;
		}
		ST.elem[low]=ST.elem[high];
		     mov++;

		while(low<high&&ST.elem[low]<=ST.elem[0])
		{	
			++low;
			cmp++;
		}
		ST.elem[high]=ST.elem[low];
		mov++;
	}
	ST.elem[low]=ST.elem[0];
       mov++;
	return low;
}

void QSort(SSTable &ST,int low,int high){
	int mid;

	if(low<high)
	{
		mid=Partition(ST,low,high);
		QSort(ST,low,mid-1);
		QSort(ST,mid+1,high);
	}
			
	
}

void QuickSort(SSTable &ST){
	int m;
	mov=0;
	cmp=0;
	QSort(ST,1,ST.length);
	printf("快速排序的: ");
//	for(m=1;m<=ST.length;m++)
	//	printf("%d ",ST.elem[m]);
	printf("比较次数： ");
		printf("%d      ",cmp);
		printf("移动次数： ");
		printf("%d      ",mov);
		printf("\n");
}

void QKSort(int n,int arry[]){
	SSTable ST;
	Creat(&ST,n,arry);
	QuickSort(ST);
}







/*希尔排序*/
//typedef struct /*静态查找表的顺序存储结构 */ 
//{ 
//ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */ 
//int length; /* 表长度 */ 
//}SSTable; 

void Creat1(SSTable *ST,int n,int b[]) 
{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */ 
	int i; 
	(*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */ 
	if(!(*ST).elem) 
		{printf("ERROR\n");exit(0);} /*内存分配失败结束程序*/ 
	for(i=1;i<=n;i++) 
	{ 
		 
		*((*ST).elem+i)=b[i]; /* 依次赋值给ST */ 
	} 
	(*ST).length=n; 
}

void ShellInsert(SSTable &ST,int dk){
	int i,j;
	for(i=dk+1;i<=ST.length;++i){
		if(ST.elem[i]<ST.elem[i-dk]){
			ST.elem[0]=ST.elem[i];
			cmp++;
			mov++;
			for(j=i-dk;j>0&&(ST.elem[0]<ST.elem[j]);j-=dk)
			{ 
				ST.elem[j+dk]=ST.elem[j];
			    cmp++;
				mov++;
			}
			ST.elem[j+dk]=ST.elem[0];
			 mov++;
			}
		cmp++;
		//for(j=1;j<=ST.length;j++)
		//printf("%d ",ST.elem[j]);
		//printf("\n");
	}
}

void ShellOder(int a,int arry[]){
	SSTable ST;
	int m,dk;
     mov=0;
	 cmp=0;
	Creat1(&ST,a,arry);
	dk=a;
	while(dk!=1){
	dk=a/2;
	a=a/2;
	ShellInsert(ST,dk);}
	printf("希尔排序的: ");
//	for(m=1;m<=ST.length;m++)
//	printf("%d ",ST.elem[m]);
	printf("比较次数： ");
	printf("%d      ",cmp);
	printf("移动次数： ");
	printf("%d      ",mov);
	printf("\n");
	
}
main()
{  srand( (unsigned)time( NULL ) ); 
	int n ;   
	int i;
    int arry[1000];
	int a;
	
	do{
    printf("输入要排序数字的个数： ");
  	scanf("%d",&n);
    //printf("输入要排序的%d个数字: ",n);
	for(i=1;i<=n;i++)
	{
		arry[i]=rand();
	//printf("%d ",arry[i]);
	}
//	scanf("%d",&arry[i]);
//	for(i=1;i<=n;i++)
//	printf("%d",arry[i]);
	printf("\n");
    ShellOder(n,arry);/*希尔排序*/
    QKSort(n,arry);
	SimpleSSort( n,arry);
	BinaryInsSort(n,arry);
	BubSort(n,arry);
	GoMerge(arry,n);
	GoHeapSort(arry,n);

	printf("按 1 继续比较，按 0 推出比较 ");
	scanf("%d",&a);
	} while(a!=0);
	return 1;
}