各种排序算法的实现(C语言实现)

/*
 * 各种基本排序算法实现(以由小到大为例)
 */

#include<stdio.h>
#define ARRAY_LENGTH 50 

//插入排序
void inseartSort(int a[],int length)
{
	int i,j,index,temp;
	for(i=0;i<length;i++){//数组a中元素逐个有序插入数组a
		for(j=0;j<i;j++) //寻找第i个元素的插入位置
			if(a[i]<a[j])
				break;
		index=j;
		temp=a[i];
		for(j=i;j>index;j--)//移位
			a[j]=a[j-1];
		a[index]=temp;
	}
}

//快速排序
void quickSort(int a[],int length)
{
    int i=0,j=length-1; //i指向数组头元素，j指向数组尾元素
	int index=0;     //指向中间值
	int m=0;         //双向搜索，判断是i加还是j减
	if(length<=0)
		return;
	while(i<=j){ //一趟快速排序
		if(!m){
            if(a[j]<a[index]){//交换a[j]和a[index]
    			a[j]=a[index]+a[j];
	    		a[index]=a[j]-a[index];
	    		a[j]=a[j]-a[index];
		     	index=j;
				m=1;
			}
        	j--;
		}else{
			if(a[i]>a[index]){
    			a[i]=a[index]+a[i];
	    		a[index]=a[i]-a[index];
	    		a[i]=a[i]-a[index];
		     	index=i;
				m=0;
			}
			i++;
		}
	}
	quickSort(a,index);
	quickSort(a+index+1,length-index-1);
}

//希尔排序
void shellSort(int a[],int length)
{
	int b[ARRAY_LENGTH]; //辅助数组
	int d,k,j,i;
	d=length/2;          //增量
	while(d>0){
		for(k=0;k<d;k++){
			j=0;
			for(i=k;i<length;i+=d)//把a中要排序的元素复制到b数组
				b[j++]=a[i];
			inseartSort(b,j);
			j=0;
			for(i=k;i<length;i+=d)//把排好序的元素放回a数组
				a[i]=b[j++];
		}
		if(d==1)//增量为1，最后一趟插入排序排完
		    break;
		d/=2;
		if(d==0)
			d=1;
	}
}

//归并排序
void mergeSort(int a[],int length)
{
	int d=2,i; //d为归并的子列中每一个子列包含的元素个数
	while(d<length){
		for(i=0;i+d<=length;i+=d) //一趟归并
			inseartSort(a+i,d);
		d*=2;
	}
	//收尾处理，因为可能有没处理完的子列(这个子列的元素个数小于d)
	inseartSort(a,length); 
}

//基数排序
void radixSort(int a[],int length)
{
	int b[ARRAY_LENGTH]; //存放a中元素取出的各个位数上的数字
	int i,index,j,temp,step=1;
    for(i=0;i<length;i++)//a中各个元素复制到b
    	b[i]=a[i];

    while(1){
    	for(i=0;i<length;i++)//取b中各个元素的个位数
    		b[i]=b[i]%10;
    	//对b数组进行排序,a数组按各个位数上的数字大小进行排序
        for(i=0;i<length;i++){
            index=i;
    		for(j=i;j<length;j++)
	    		if(b[j]<b[index])
		    		index=j;
    		temp=b[i];
    		b[i]=b[index];
     		b[index]=temp;
    		temp=a[i];
    		a[i]=a[index];
    		a[index]=temp;
		}
    	for(i=0;i<length;i++)
    		b[i]=a[i]/(10*step);

    	for(i=0;i<length;i++)//判断b中的元素是否全是0
	    	if(b[i]!=0)
	    		break;
    	if(i==length)//b中元素全是0
    		break;
		step*=10;
	}
}


/*********************** 以下是堆排序的实现 ***********************/

//筛选法调整堆,i指向要调整的元素
void sift(int a[],int length,int i)
{
	int j=2*(i+1)-1;  //j指向i的左孩子
	int index=j;    //index指向某个元素的左右孩子中较大的一个
	int temp;
	if(j>=length) //i为叶子节点
		return;
	if(j+1<length)
    	index=a[j]>a[j+1]?j:j+1;
	if(a[i]<a[index]){//如果父亲结点小于孩子结点，交换
       temp=a[i];
	   a[i]=a[index];
	   a[index]=temp;
	   sift(a,length,index); //可能破坏了左子树或右子树的排序，对子树进行筛选法调整
	}
}

//堆排序(大顶堆)
void heapSort(int a[],int length)
{
	int i; //i指向要调整的元素，从length/2开始
    int temp;

	//从length/2个元素开始调整堆
	for(i=length/2-1;i>=0;i--){
        sift(a,length,i);
	}

	//取堆顶元素,最后一个元素代替第一个元素。然后调整堆 
	for(i=length-1;i>0;i--){
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;
		sift(a,i,0);
	}
}
/*********************** 以上是堆排序的实现 ***********************/


void main()
{
	int i;
	int a[]={5,3,5,6,12,33,24,10,22,8};
	int b[10];

	//待排序序列
	printf("待排序序列：");
    for(i=0;i<10;i++)
		b[i]=a[i];
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");

	//测试插入排序
	printf("插入排序  ：");
	inseartSort(b,10);
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");

	//测试快速排序
	printf("快速排序  ：");
    for(i=0;i<10;i++)
		b[i]=a[i];
	quickSort(b,10);
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");

	//测试希尔排序
	printf("希尔排序  ：");
    for(i=0;i<10;i++)
		b[i]=a[i];
	shellSort(b,10);
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");

	//测试归并排序
	printf("归并排序  ：");
    for(i=0;i<10;i++)
		b[i]=a[i];
	mergeSort(b,10);
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");

	//测试基数排序
	printf("基数排序  ：");
    for(i=0;i<10;i++)
		b[i]=a[i];
	radixSort(b,10);
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");

	//测试堆排序
	printf("堆排序    ：");
    for(i=0;i<10;i++)
		b[i]=a[i];
	heapSort(b,10);
	for(i=0;i<10;i++)
		printf("%-4d",b[i]);
    printf("\n\n");
}