欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

数据结构内部排序算法的性能分析

程序员文章站 2022-05-26 11:33:38
...

  【 昨天在整理资料的时候，刚好整理到数据结构的内部排序算法这一块，主要内容为对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较，仅供初学数据结构的新手浏览学习，哪里写的不对的地方，请大神指点；之前学习内部排序算法的时候距离写这篇博客隔了挺长时间，有什么不好的地方，请评论，一定虚心改正】

简介：

本博客分为三部分：

  1. 第一部分:内部排序算法的性能分析问题描述及要求；

  2. 第二部分：代码实现及运行结果（开发环境  Dev-C++）；

  3. 第三部分：内部排序算法的总结；

 

正文：

第一部分:内部排序算法的性能分析问题描述及要求；

【问题描述】

设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。

【基本要求】

(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；

(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；

(3)输出比较结果；

(4)验证各算法每次排序的稳定性；

(5)输出界面的优化。

 第二部分：代码实现及运行结果；

（音乐和界面那一块代码重复特别多，当初是为了验收课设凑得代码数，仅供参考）

总体思想，帮助理解代码：

数据结构内部排序算法的性能分析

/*头文件和宏定义部分*/
#include"string.h"
#include"ctype.h"
#include"time.h"
#include"malloc.h" /* malloc()等 */
#include"limits.h" /* INT_MAX等 
*/
#include"stdio.h" /* EOF(=^Z或F6),NULL */
#include"stdlib.h" /* atoi() */
#include"io.h" /* eof() */
#include"math.h" /* floor(),ceil(),abs() */
#include"process.h" /* exit() */
/* 函数结果状态代码 */

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAXSIZE 100   //示例数据类型的最大长度
/*音乐   界面*/
#include<windows.h>
#define I 20 
#define R 250 
#include<conio.h>

typedef int KeyType;		//定义关键字类型为整数类型
typedef int InfoType;	//定义关键字类型为整数类型
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef struct{
	KeyType key;	//关键字项
	InfoType otherinfo;		//其它数据项
}RedType;		//记录类型

typedef struct {
	RedType r[MAXSIZE+1];		//r[0]闲置或用作哨兵单元
	int length;		//顺序表长度
}SqList;		//顺序表类型

/*定义1/8时间长度为225ms，中速*/
const unsigned PER = 225;
 
/*定义音阶：低音*/
enum {Do = 262,Re = 294,Mi = 330,Fa = 349,So = 392,La = 440,Xi = 494};
/*定义播放一节音符的函数
f--表示音符，其值为上述定义的枚举型
a--	表示音高，其值为1(低音)、2(中音)、3(高音)
*/
void Play(int f,int a,int t)
{
	int i = 0;
	Beep((unsigned )(f*a),t*PER);
}
 
/*定义休止函数*/
void Stop(int t)
{
	Sleep(t*PER);
}

void happysong1()
{
		/*欢乐颂，第一段*/
		/*第一节:3 3 4 5*/
		Play(Mi,2,2); Play(Mi,2,2); Play(Fa,2,2); Play(So,2,2);
 
		/*第二节:5 4 3 2*/
		Play(So,2,2); Play(Fa,2,2); Play(Mi,2,2); Play(Re,2,2);
 
		/*第三节:1 1 2 3*/
		Play(Do,2,2); Play(Do,2,2); Play(Re,2,2); Play(Mi,2,2);
 
		/*第四节:3 2 2 -*/
		Play(Mi,2,2); Play(Re,2,2); Play(Re,2,4); 
		
}

void happysong2()
{
		/*欢乐颂第二段*/
		/*第一节:3 3 4 5*/
		Play(Mi,2,2); Play(Mi,2,2); Play(Fa,2,2); Play(So,2,2);
 
		/*第二节:5 4 3 2*/
		Play(So,2,2); Play(Fa,2,2); Play(Mi,2,2); Play(Re,2,2);
 
		/*第三节:1 1 2 3*/
		Play(Do,2,2); Play(Do,2,2); Play(Re,2,2); Play(Mi,2,2);
 
		/*第四节:2 1 1 -*/
		Play(Re,2,2); Play(Do,2,2); Play(Do,2,2); 
}

void InitData(SqList *L,int dataCopy[])
{
	int i;
	L->length=MAXSIZE;
	srand((unsigned)time(NULL)); 
	for(i=0;i<=MAXSIZE;i++)
	{
		L->r[i].otherinfo=0;
		dataCopy[i]=L->r[i].key=rand();
	}
}

void PrintData(SqList L)
{
	int i;
	for(i=1;i<=L.length;i++)
	{
		printf("%d\t",L.r[i].key);
	}
}

void ResumeData(SqList *L,int dataCopy[])
{
	int i;
	for(i=0;i<=MAXSIZE;i++)
	{
		L->r[i].key=dataCopy[i];
	}
}
int p1_c=0;
int p1_m=0;
int p2_c=0;
int p2_m=0;
int p3_c=0;
int p3_m=0;
int p4_c=0;
int p4_m=0;
int p5_c=0;
int p5_m=0;
int p6_c=0;
int p6_m=0;
void PrintStatistic(int *compareCounts,int *moveCounts)
{
	p1_c+=compareCounts[0];
	p2_c+=compareCounts[1];
	p3_c+=compareCounts[2];
	p4_c+=compareCounts[3];
	p5_c+=compareCounts[4];
	p6_c+=compareCounts[5];
	p1_m+= moveCounts[0];
	p2_m+= moveCounts[1];
	p3_m+= moveCounts[2];
	p4_m+= moveCounts[3];
	p5_m+= moveCounts[4];
	p6_m+= moveCounts[5];
	printf("\n\t\t各种排序方法比较结果:\n\n");
	printf("\t\t起泡排序:    比较次数  %d,移动次数  %d\n",compareCounts[0],moveCounts[0]);
	printf("\t\t直接插入排序:比较次数  %d,移动次数  %d\n",compareCounts[1],moveCounts[1]);
	printf("\t\t简单选择排序:比较次数  %d,移动次数  %d\n",compareCounts[2],moveCounts[2]);
	printf("\t\t快速排序:    比较次数  %d,移动次数  %d\n",compareCounts[3],moveCounts[3]);
	printf("\t\t希尔排序:    比较次数  %d,移动次数  %d\n",compareCounts[4],moveCounts[4]);
	printf("\t\t堆排序:      比较次数  %d,移动次数  %d\n",compareCounts[5],moveCounts[5]);
}



/*******************************直接插入排序*******************************/

void InsertSort(SqList *L,int *compareCounts,int *moveCounts )		//直接插入排序
{
	int i,j;		//
	for(i=2;i<=L->length;i++)		//从顺序表的第二个元素开始进行比较
	{
		if(L->r[i].key<L->r[i-1].key)		//将每个元素与它的前一个元素关键字进行比较
		{
			L->r[0]=L->r[i];		//如果关键字比前一个元素关键字小，就将元素复制作为哨兵
			L->r[i]=L->r[i-1];
			(*moveCounts)+=2;		//关键字移动了2次
			j=i-2;		//从要比较的关键字的前第二个记录开始进行比较,然后后移
			while(L->r[0].key<L->r[j].key)
			{
				L->r[j+1]=L->r[j];		//记录后移
				(*moveCounts)++;		//每作一次后移,移动次数加1
				j--;
				(*compareCounts)++;		//每作一次比较，比较次数加1
			}
			L->r[j+1]=L->r[0];		//插入到正确位置
		}
		(*compareCounts)++;
	}
}



/*******************************希尔排序*******************************/

void ShellInsert(SqList *L,int increment,int *compareCounts,int *moveCounts)
{		//对顺序表作一趟希尔插入排序
	int j,n;
	for(j=1+increment;j<=L->length;j++)
	{
		if(L->r[j].key<L->r[j-increment].key)		//将L->[i]插入到有序增量子表
		{
			L->r[0]=L->r[j];		//暂存在L->r[0]
			L->r[j]=L->r[j-increment];
			(*moveCounts)+=2;
			for(n=j-2*increment;n>0&&L->r[0].key<L->r[n].key;n-=increment)
			{
				L->r[n+increment]=L->r[n];		//记录后移，查找插入位置
				(*moveCounts)++;
				(*compareCounts)++;
			}
			L->r[n+increment]=L->r[0];		//插入
			(*moveCounts)++;
		}
		(*compareCounts)++;
	}
}



void ShellSort(SqList *L,int IncreList[],int times,int *compareCounts,int *moveCounts)		//希尔排序
{		//按增量序列Increlist［0.....times-1］对顺序表Ｌ作希尔排序
	int k;		//
	for(k=0;k<times;k++)
	{
		ShellInsert(L,IncreList[k],compareCounts,moveCounts);		//一趟增量为IncreList[k]的插入排序
	}
}



/*******************************起泡排序*******************************/

void BubbleSort(SqList *L,int *compareCounts,int *moveCounts)		//起泡排序
{
	int i,j;
	for(i=1;i<=L->length;i++)
	{
		for(j=L->length;j>i;j--)
		{		//从后往前两两进行比较，将元素关键字小的交换到前面
			if(L->r[j].key<L->r[j-1].key)	
			{
				L->r[0]=L->r[j];
				L->r[j]=L->r[j-1];
				L->r[j-1]=L->r[0];
				(*moveCounts)+=3;
			}
			(*compareCounts)++;
		}
	}
}



/*******************************快速排序*******************************/

int Partition(SqList *L,int low,int high,int *compareCounts,int *moveCounts)		//快速排序中的分
{
	int pivotkey;
	L->r[0]=L->r[low];
	(*moveCounts)++;
	pivotkey=L->r[low].key;
	while(low<high)
	{
		while(low<high&&L->r[high].key>=pivotkey)
		{
			high--;
			(*compareCounts)++;
		}
		L->r[low]=L->r[high];
		(*moveCounts)++;
		while(low<high&&L->r[low].key<=pivotkey)
		{
			low++;
			(*compareCounts)++;
		}
		L->r[high]=L->r[low];
		(*moveCounts)++;
		(*compareCounts)++;
	}
	L->r[low]=L->r[0];
	(*moveCounts)++;
	return low;
}



void QSort(SqList *L,int low,int high,int *compareCounts,int *moveCounts)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(L,low,high,compareCounts,moveCounts);
		QSort(L,low,pivotloc-1,compareCounts,moveCounts);
		QSort(L,pivotloc+1,high,compareCounts,moveCounts);
	}
}



void QuickSort(SqList *L,int *compareCounts,int *moveCounts)
{
	QSort(L,1,L->length,compareCounts,moveCounts);
}



/*******************************简单选择排序*******************************/

void SelectSort(SqList *L,int *compareCounts,int *moveCounts)
{
	int i,j,minPoint;
	for(i=1;i<=L->length;i++)
	{
		minPoint=i;
		for(j=i+1;j<=L->length;j++)
		{
			if(L->r[j].key<L->r[minPoint].key)
			{
				minPoint=j;
			}
			(*compareCounts)++;
		}
		if(minPoint!=i)
		{
				L->r[0]=L->r[minPoint];
				L->r[minPoint]=L->r[i];
				L->r[i]=L->r[0];
				(*moveCounts)+=3;
		 } 
		(*compareCounts)++;
	}
}




/*******************************堆排序*******************************/

void HeapAdjust(SqList *L,int s,int m,int *compareCounts,int *moveCounts)
{
	RedType cmpKey;		//待比较的值
	int j;
	cmpKey=L->r[s];
	(*moveCounts)++;
	for(j=s*2;j<=m;j*=2)
	{
		(*compareCounts)+=2;
		if(j<m&&L->r[j].key<L->r[j+1].key) j++;
		if(!(cmpKey.key<L->r[j].key)) break;
		L->r[s]=L->r[j];
		(*moveCounts)++;
		s=j;		
	}
	L->r[s]=cmpKey;
	(*moveCounts)++;
}



void HeapSort(SqList *L,int *compareCounts,int *moveCounts)
{
	int i;
	RedType temp;
	for(i=L->length/2;i>0;i--)	HeapAdjust(L,i,L->length,compareCounts,moveCounts);
	for(i=L->length;i>1;i--)
	{
		temp=L->r[1];
		L->r[1]=L->r[i];
		L->r[i]=temp;
		(*moveCounts)+=3;
		HeapAdjust(L,1,i-1,compareCounts,moveCounts);
	}
}



void SortCompare()
{
	SqList L;		//用顺序表存放待排序的元素
	int dataCopy[MAXSIZE+1],i;
	int compareCounts[7],moveCounts[7];
	int increList[6];
	for(i=0;i<5;i++)
	{
		increList[i]=(int)pow(2,7-i)-1;//局部结论；增量序列 increList[i]=(int)pow(2,t+1-i)-1  t为排序趟数 
	}
	increList[5]=1;
	for(i=0;i<7;i++)
	{

		compareCounts[i]=0;
		moveCounts[i]=0;
	}
	InitData(&L,dataCopy);		//初始化数据，随机产生100个正整数的数列
	printf("\t\t\t初始化数据后产生的数列:\n");		
	PrintData(L);		//显示出未排序的数列

	printf("\n\n\t\t\t经过起泡排序后产生的数列:\n");
	BubbleSort(&L,&compareCounts[0],&moveCounts[0]);		//对数列使用起泡排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过直接插入排序后产生的数列:\n");
	InsertSort(&L,&compareCounts[1],&moveCounts[1]);		//对数列使用插入排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过简单选择排序后产生的数列:\n");
	SelectSort(&L,&compareCounts[2],&moveCounts[2]);		//对数列使用简单选择排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过快速排序后产生的数列:\n");
	QuickSort(&L,&compareCounts[3],&moveCounts[3]);		//对数列使用快速排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过希尔排序后产生的数列:\n");
	ShellSort(&L,increList,6,&compareCounts[4],&moveCounts[4]);		//对数列使用希尔排序
	PrintData(L);		//显示出排序好的数列
	ResumeData(&L,dataCopy);

	printf("\n\n\t\t\t经过堆排序后产生的数列:\n");
	HeapSort(&L,&compareCounts[5],&moveCounts[5]);		//对数列使用堆排序
	PrintData(L);		//显示出排序好的数列
	PrintStatistic(compareCounts,moveCounts);
}

void tuxing()
{
	int i,j,e,a; 
	for(i=1,a=I;i<I/2;i++,a--)
	{ 
	for(j=(int) ( I-sqrt((double)(I*I-(a-i)*(a-i))) );j>0;j--) 
	printf(" "); 
	for(e=1;e<=2*sqrt((double)(I*I-(a-i)*(a-i)));e++) 
	printf("\3");
	for(j=(int) ( 2*( I-sqrt((double)(I*I-(a-i)*(a-i))) ) );j>0;j--) 
	printf(" ");
	for(e=1;e<=2*sqrt( (double) (I*I-(a-i)*(a-i)) );e++) 
	printf("\3");
	printf("\n"); 
	} 
	for(i=1;i<80;i++)
	{
		if(i==25) 
		{
		printf("^~~~^小组成员的名字^~~~^");
		i+=30;
		}

	printf("\3");
	}
	printf("\n"); 
	for(i=1;i<=R/2;i++)
	{ 
	if(i%2||i%3)continue;
	for(j=(int) ( R-sqrt( (double) (R*R-i*i) ) );j>0;j--) 
	printf(" "); 
	for(e=1;e<=2*( sqrt( (double)(R*R-i*i) )- (R-2*I) );e++) 
	printf("\3");
	printf("\n"); 
	} 
//下面的是以time做时间变量来控制变色

	long time; 
	for(; ;) 
	{ 
	system("color c");  //system头文件<process.h> 或<stdlib.h>
	for(time=0;time<20;time++); 
	system("color e");
	for(time=0;time<10;time++);
	system("color a");
	for(time=0;time<20;time++);
	system("color d");
	for(time=0;time<20;time++);
	system("color e");
	for(time=0;time<10;time++);
	system("color e");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color a");
	for(time=0;time<20;time++);
	system("color d");
	for(time=0;time<10;time++);
	system("color 0");
	for(time=0;time<10;time++);
	system("color 1");
	for(time=0;time<10;time++);
	system("color 2");
	for(time=0;time<5;time++);
	system("color 3");
	for(time=0;time<10;time++);
	system("color 4");
	for(time=0;time<10;time++);
	system("color 5");
	for(time=0;time<15;time++);
	system("color 6");
	for(time=0;time<10;time++);
	system("color 5");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color b");
	for(time=0;time<10;time++);
	system("color d");
	for(time=0;time<10;time++);
	system("color 5");
	for(time=0;time<10;time++);
	system("color 5");
	for(time=0;time<10;time++);
	system("color b");
	for(time=0;time<10;time++);
	system("color a");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<20;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color e");
	for(time=0;time<10;time++);
	system("color e");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<20;time++);
	system("color f");
	for(time=0;time<10;time++);
	system("color 0");
	for(time=0;time<10;time++);
	system("color 1");
	for(time=0;time<10;time++);
	system("color 2");
	for(time=0;time<5;time++);
	system("color 3");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color b");
	for(time=0;time<10;time++);
	system("color 9");
	for(time=0;time<5;time++);
	system("color 0b");
	for(time=0;time<5;time++);
	system("color 0c");
	for(time=0;time<5;time++);
	system("color 0d");
	for(time=0;time<10;time++);
	system("color 0e");
	for(time=0;time<5;time++);
	system("color 9");
	for(time=0;time<8;time++);
	for(time=0;time<10;time++);
	system("color b");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color c");
	for(time=0;time<10;time++);
	system("color b");
	for(time=0;time<10;time++);
	system("color 9");
	for(time=0;time<5;time++);
	system("color 0b");
	for(time=0;time<5;time++);
	system("color 0c");
	for(time=0;time<5;time++);
	system("color 0b");
	for(time=0;time<10;time++);
	system("color 0e");
	for(time=0;time<5;time++);
	system("color 0c");
	for(time=0;time<8;time++);
	for(time=0;time<5;time++);
	system("color 0c");
	for(time=0;time<5;time++);
	system("color 0d");
	for(time=0;time<10;time++);
	system("color 0e");
	for(time=0;time<10;time++);
	system("color 2");
	for(time=0;time<5;time++);
	system("color 3");
	break;
	}
	}
void AVG(){
		    system("cls"); 
			printf("                经过五次比较得出以下平均值\n"); 
			printf("\t\t起泡排序:    平均比较  %d次,平均移动  %d次\n",p1_c/5,p1_m/5);
			printf("\t\t直接插入排序:平均比较  %d次,平均移动  %d次\n",p2_c/5,p2_m/5);
			printf("\t\t简单选择排序:平均比较  %d次,平均移动  %d次\n",p3_c/5,p3_m/5);
			printf("\t\t快速排序:    平均比较  %d次, 平均移动  %d次\n",p4_c/5,p4_m/5);
			printf("\t\t希尔排序:    平均比较  %d次, 平均移动  %d次\n",p5_c/5,p5_m/5);
			printf("\t\t堆排序:      平均比较  %d次,平均移动  %d次\n",p6_c/5,p6_m/5);
			printf("按任意键查看算法总结");
			getch();
}


void zongjie(){
  system("cls"); 
  system("color a"); 
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("☆");Sleep(30);
  printf("★");Sleep(30);
  printf("\n\n\n");
	printf("                                               总结\n"); 
	printf("     ________________________________________________________________________________________________\n");
	printf("\n"); 
	printf("                      排序方法          空间复杂度          稳定性          复杂度\n");
	printf("\n");
	printf("\n");
	printf("                   直接插入排序           O(n)                稳定            简单\n");
	printf("\n");
	printf("\n");
	printf("                   简单选择排序           O(n*n)              不稳定          简单\n");
	printf("\n");
	printf("\n");
	printf("                    快速排序              O(nlogn)            不稳定          较复杂\n");
	printf("\n");
	printf("\n");
	printf("                    希尔排序              O(nlogn)            不稳定          复杂\n");
	printf("\n");
	printf("\n");
	printf("                    冒泡排序              O(n*n)              稳定            简单\n");
	printf("\n");
	printf("\n");
	printf("                    堆排序                O(nlgn)             不稳定          复杂\n");
	printf("\n");
	printf("     _________________________________________________________________________________________________\n\n\n");
      printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("★");Sleep(30);
	  printf("☆");Sleep(30);
	  printf("☆");Sleep(30);
      printf("★");Sleep(30);
      printf("☆");Sleep(30);

}
main()	
{
	int i,temp;
	int ggg=1;
	int y=1;
	happysong1();
	happysong2();
	while(ggg>0)
	{
	    tuxing();	
	    
	    printf("继续进行请按1"); 
	    scanf("%d",&y);
	    if(y==1)
	      break;
	} 
	 while(y==1){

	for(i=0;i<5;i++)
	{
		SortCompare();
		printf("\n\t\t请按任意键进行下一组数据的排序对比\n\n");
		temp=getchar();
		if(i==4){	
		    AVG();
			zongjie();
		}
	}break;	} 
}

运行结果：（以一次比较次数为例）

数据结构内部排序算法的性能分析

数据结构内部排序算法的性能分析

第三部分：内部排序算法的总结；

（1）起泡排序基本思想：

思路：设待排序元素序列中的元素个数为n，从后向前两两比较相邻元素的值，如果发生逆序（即前一个大于后一个），则交换它们，直到序列比较完，称之为一趟起泡，结果将最小的元素交换到待排序元素序列的第一个位置，其他元素也都向排序的最终位置移动。下一趟起泡时前一趟确定的最小元素不再参加比较，带排序序列减少一个元素，一趟起泡的结果又把序列中最小的元素排到序列的第一个位置……这样最多做n-1趟起泡就能把所有元素排好序。

当然，在个别情况下，元素有可能在排序中途向相反的方向移动，但元素的总趋势是向最终位置移动。

  1. 堆排序基本思想：

思路：堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。其基本思想为(大顶堆)：将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

（3）直接插入排序

   思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.

（4） 希尔排序

思路：先取一个正整数d1(d1<n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2<d1),重复上述分组和排序操作,直到取di=1(>=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=1

（5）快速排序:（递归和非递归）

思路先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束。

在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止

（6）简单选择排序：

思路：（选出最小值，放在第一位，然后第一位向后推移，如此循环）第一位与后面每一个逐个比较，每次都使最小的置顶，第一位向后推进（即刚选定的第一位是最小值，不再参与比较，比较次数减1）

 

（大概就是这样子啦，要是有回头有啥想改动的，会在来改动的~）

相关标签： 数据结构 C语言 内部排序算法性能分析 比较

上一篇： 修改windows文件的换行符

下一篇： springboot中mybatis****与分页的应用

推荐阅读