编辑代码

#include<stdio.h>
#define LeftChild(i) (2*(i)+1)//堆排序，定义一个宏，便于取得左孩子下标 

/*直接插入排序*/ 
void InsertionSort(int *pData,int n)//直接插入排序（递增） 
{//pData待排序的数据，这里为指向一个整型数组的指针		n为关键字数量 
	int temp, i, j;
	for(i=1; i<n; i++)//对于N个关键字，进行N-1次比较 
	{
		temp=pData[i];//保存待插入关键字 ，是从第二个开始做关键字的，然后j取数组第一个开始比较，因为如果关键字是需要插到前边，则需要把比关键字大的后移，然后覆盖掉原来的关键字 
		for(j=i-1; j>=0&&temp<pData[j]; j--)//往后移动关键字，以便于找到正确的插入位置 		
		{
			pData[j+1]=pData[j];
		}
		pData[j+1]=temp;
	}
}

/*希尔排序*/
void ShellSort(int *pData, int n, int delta)//希尔排序 
{//n关键字数量，delta用以希尔排序的增量 
	int temp, i, j;
	for(i=delta; i<n; i++)
	{
		temp=pData[i];
		for(j=i-delta; j>=0&&temp<pData[j]; j=j-delta)
			pData[j+delta]=pData[j];
		pData[j+delta]=temp;
	}
}

/*快速排序*/
int partition(int a[], int i, int j)
{//a待划分的数据，这里为指向一个整形数组的指针	 i待划分序首元素下标	j待划分序列尾元素下标	 
	int temp=a[i];//选择首元素为划分元素 
	while(i<j)//当i>=j时结束本次元素划分 
	{
		while(a[j]>=temp&&i<j)//从前往后找到第一个小于划分元素的元素 
			j--;
		if(i<j)//若找到则移动元素，并把下标加1 
			a[i++]=a[j];
		while(a[i]<=temp&&i<j)//从前往后找到第一个大于划分元素的元素 
			i++;
		if(i<j)
			a[j--]=a[i];
	}
	a[i]=temp;
	return i;
}
void QuickSort(int a[], int i, int j)
{//a待排序的数据，这里为指向一个整形数组的指针	 i待排序序首元素下标	j待排序序列尾元素下标
	int k;
	if(i<j)
	{
		k=partition(a,i,j);
		QuickSort(a,i,k-1);
		QuickSort(a,k+1,j);
	}
}

/*堆排序*/ 
void BuildDown(int a[], int n, int rootIndex)
{//a待排序的数据，这里为指向一个整形数组的指针		n关键字数量		rootindex根节点下标 
	int root=a[rootIndex];
	int childIndex=LeftChild(rootIndex);
	while(childIndex<n)
	{
		if(childIndex!=n-1&&a[childIndex+1]>a[childIndex])
			childIndex++;
		if(root<a[childIndex])
		{
			a[rootIndex]=a[childIndex];
			rootIndex=childIndex;
			childIndex=LeftChild(rootIndex);
		}
		else
			break;
	}
	a[rootIndex]=root;
}
void HeapSort(int a[],int n)
{//a待排序的数据，这里为指向一个整形数组的指针		n关键字数量
	int temp, rootIndex, i;
	for(rootIndex= (n-2)/2; rootIndex>=0; rootIndex--)
		BuildDown(a, n, rootIndex);
	for(i= n-1; i>=0; i--)
	{
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;
		BuildDown(a, i, 0);
	}
}


int main()
{
	/*直接插入排序（递增）*/ 
	printf("*******直接插入排序如下*******\n\n"); 
	
	int data[100], n=0, x=0/*单纯用来控制循环*/;
	printf("请输入要排序数字的个数：\n");
	scanf("%d",&n);
	printf("请输入元素（中间按空格隔开）：");
	for(x=0; x<n; x++) 
	{
		scanf("%d",&data[x]);
//检验输入		printf("%d",data[x]);
	} 
	InsertionSort(data,n);
	printf("排序完成：");
	for(x=0; x<n; x++)
	{
		printf("%d ",data[x]);
	}
	printf("\n\n*******（这是分割线）*******"); 
	printf("\n\n\n");
	
	
	printf("*******希尔排序如下*******\n"); 
	/*希尔排序，多次调用效果更佳...留待读者自己也就是我实现...*/
	
	printf("请输入要排序数字的个数：\n");
	scanf("%d",&n);
	printf("请输入元素（中间按空格隔开）：");
	for(x=0; x<n; x++)
	{
		scanf("%d",&data[x]);
	}
	int increment=n/3;
	for(;increment>0;increment=increment/3)
	{
		ShellSort(data, n, increment);
	}
	if(increment==0)
	{
		InsertionSort(data,n);
	}
	//ShellSort(data, n, increment);
	printf("排序完成：");
	for(x=0; x<n; x++)
	{
		printf("%d ",data[x]);
	}
	printf("\n\n*******（这是分割线）*******"); 
	printf("\n\n\n");
	
	
	printf("*******快速排序如下*******\n"); 
	
	printf("请输入要排序数字的个数：\n");
	scanf("%d",&n);
	printf("请输入元素（中间按空格隔开）：");
	for(x=0; x<n; x++)
	{
		scanf("%d",&data[x]);
	}
	QuickSort(data, 0, n-1);
	printf("排序完成：");
	for(x=0; x<n; x++)
	{
		printf("%d ",data[x]);
	}
	printf("\n\n*******（这是分割线）*******"); 
	printf("\n\n\n");
	
	
	printf("*******堆排序如下*******\n");
	printf("请输入要排序数字的个数：\n");
	scanf("%d",&n);
	printf("请输入元素（中间按空格隔开）：");
	for(x=0; x<n; x++)
	{
		scanf("%d",&data[x]);
	}
	HeapSort(data, n);
	printf("排序完成：");
	for(x=0; x<n; x++)
	{
		printf("%d ",data[x]);
	}
	
	return 0;
}