插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序算法比较

//插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define M 1000

int shu[M];  //存放要排序的数组
int chang;  //存放要排序的数组的长度

//-------------------------显示输出----------------------------
void show()  
{
	printf("\n排序后的数为：\n");
	for (int i=1; i<=chang; i++)
		printf("%d ", shu[i]);
	printf("\n\n排序结束!\n");
}

//--------------------------插入排序-----------------------------
void cha_ru()  
{
	for (int i=2, j; i<=chang; i++)
		if(shu[i] < shu[i-1])
		{
			shu[0] = shu[i];  //将待查找的数放入监视哨里面
			j = i - 1;
			while(shu[0] < shu[j])  //寻找插入位置
			{
				shu[j+1] = shu[j];
				j--;
			}
			shu[j+1] = shu[0];  //将元素插入
		}
}

//--------------------------冒泡排序---------------------------
void mao_pao()  
{
	int change = 1;  //标记一轮遍历后是否有元素进行交换
	for (int i=1; i<=chang && change; i++)
	{
		change = 0;
		for (int j=1; j<=chang-i; j++)
			if(shu[j] > shu[j+1])
			{
				shu[0] = shu[j];
				shu[j] = shu[j+1];
				shu[j+1] = shu[0];
				change = 1;
			}
	}
}

//--------------------------选择排序----------------------------
void xuan_ze()  
{
	int min;        //每次测试时最小的变量的代号
	int temp;
	for (int i=1; i<=chang; i++)
	{
		min = i;    //shu[min]记录最小的shu[i]
		for (int j=i+1; j<=chang; j++)
			if(shu[j] < shu[min])
				min = j;  //修改min
	    if(min != i)      //若min!=i  则将shu[min]与shu[i]进行交换
		{
			temp = shu[min];
			shu[min] = shu[i];
			shu[i] = temp;
		}
	}

}

//--------------------------快速排序------------------------------
int kuaisu_pass(int low, int high)//快速排序过程
{
	int x = shu[low];
	while(low < high)
	{
		while(low<high && shu[high]>=x) //high从右到左找小于x的记录
    		high--;
		if(low < high)   //找到小于x的记录进行交换
		{
			shu[low] = shu[high];
			low++;
		}
		while(low<high && shu[low]<=x)  //low从左到右找大于x的记录
            low++;
		if(low < high)   //找到大于x的记录进行交换
		{
			shu[high] = shu[low];
			high--;
		}	
	}
	shu[low] = x;
	return low;   
}

void kuai_su(int low, int high)  //快速排序主函数
{
	int pos;
	if(low < high)
	{
		pos = kuaisu_pass(low, high);
		kuai_su(low,pos-1);
		kuai_su(pos+1,high);
	}
}

//----------------------------堆排序------------------------------
void chong_jian_dui(int k, int m)  //重建堆
{
	int x = shu[k];  //暂存“根”记录
	int i = k;
	int j = 2 * k;
	int finished = 0;
	while (j<=m && !finished)
	{
		if(j<m && shu[j]<shu[j+1]) //若存在右子树，且右子树根的关键字大，则延右分支“筛选"
			j = j + 1;
		if(x > shu[j])  //筛选完毕
			finished = 1;
		else
		{
			shu[i] = shu[j];
			i = j;
			j = 2 * i;
		}
	}
	shu[i] = x;   //将shu[k]填到恰当的位置
}

void jian_dui()   //建堆
{
	int n = chang;
	for (int i=n/2; i>=1; i--)  //自第【n/2】个记录开始进行筛选建堆
		chong_jian_dui(i,n);	
}

void dui()  //堆排序主函数
{
	int n = chang; //将要排序的数存储到N中
	int temp;
	jian_dui();   //将堆建立
	for (int i=n; i>=2; i--)  //将堆顶记录和堆中的最后一个记录交换
	{
		temp = shu[1];
		shu[1] = shu[i];
		shu[i] = temp;
		chong_jian_dui(1,i-1);  //进行调整，使得shu[1]到shu[i-1]变成堆
	}
}

//--------------------------归并排序-------------------------------
void gui_bing_way(int temp1[], int temp2[], int begin, int half, int end)//二路归并过程
{
	for (int j=half+1,k=begin; begin<=half && j<=end; k++)
	{                                   //将temp2[]中的记录由小到大地并入temp1[]中
		if (temp2[begin] < temp2[j])
			temp1[k] = temp2[begin++];
		else
			temp1[k] = temp2[j++];
	}
	for(; begin<=half;begin++, k++)  //将剩余的temp2[begin...half]复制到到temp1[]中
		temp1[k] = temp2[begin];
	for(; j<=end; j++, k++)          //将剩余的temp2[j....end]复制到temp1[]中
		temp1[k] = temp2[j];
			
}

void gui_bing(int temp1[],int temp2[],int begin, int end)   //归并排序
{
	int half;
	if(begin == end)
		temp2[begin] = temp1[begin];
	else
	{
		half = (begin + end) / 2;   //将temp2[begin...end]平分为temp2[begin...half]和temp2[half+1....end]
		gui_bing(temp1,temp2,begin,half);  //递归将temp2[begin...half] 归并
		gui_bing(temp1,temp2,half+1,end);   //递归将temp2[half+1...end]  归并
		gui_bing_way(temp1,temp2,begin,half,end); //将temp2[begin..half]和temp2[half+1..end]归并到temp1[begin..end]中
	}
	for (int i=1; i<=chang; i++)  //将归并后的数存入temp2[]中
		temp2[i] = temp1[i];
}

//------------------------------主函数-----------------------------
int main()
{
    int temp_shu[M];
	int choise;  //排序方式的选择
	int temp = 1;
	printf("请输入要排序的随机数的个数：");
	scanf("%d", &chang);
	srand((unsigned)time(NULL));
	for (int i=1; i<=chang; i++)
		shu[i] = rand()%1000;
	printf("随即数的初始状态为:\n");
	for (i=1; i<=chang; i++)   //将随机数存储到temp_shu[]中，并显示
	{
		temp_shu[i] = shu[i];
		printf("%d ", shu[i]);
	}
	printf("\n\n请选择要排序的方式：\n1.插入排序\n2.冒泡排序\n3.选择排序\n4.快速排序\n5.堆排序\n6.归并排序\n请选择：");
	scanf("%d", &choise);
	while(temp)
	{
		switch(choise)
		{
		case 1:       //插入排序
			cha_ru();   
			temp = 0;
			break;
		case 2:       //冒泡排序
			mao_pao();  
			temp = 0;
			break;
		case 3:       //选择排序
			xuan_ze();
			temp = 0;
			break;
		case 4:       //快速排序
			kuai_su(1,chang);
			temp = 0;
			break;
		case 5:      //堆排序
			dui();
			temp = 0;
			break;
		case 6:     //归并排序
			gui_bing(shu,temp_shu,1,chang);
			temp = 0;
			break;
		default:   //其他错误输入
			printf("输入错误，请重新输入!\n");
			printf("\n请选择要排序的方式：\n1.插入排序\n2.冒泡排序\n3.选择排序\n4.快速排序\n5.堆排序\n6.归并排序\n");
			scanf("%d", &choise);
			break;
		}
	}
	show();   //显示输出
	return 0;
}           

欢迎大家转载，如有转载请注明文章来自：   http://blog.csdn.net/q345852047