quicksort.h

快速排序、合并排序、插入排序、堆排序、计数排序等算法的C语言实现

#include<stdio.h>
#define TRUE 1
#define FALSE 0

//快速排序头文件
typedef int ElemType;

long Partition(ElemType A[],long p,long r)
{//划分数组
	long i,j;
	ElemType temp1,temp2;
	temp1=A[r];
	i=p-1;
	for(j=p;j<r;j++)
	{
		if(A[j]<=temp1)
		{
			i++;
			ElemType t;
			t=A[i];
			A[i]=A[j];
			A[j]=t;
		}
	}
	temp2=A[i+1];
	A[i+1]=A[r];
	A[r]=temp2;
	return i+1;
}

void QuickSort(ElemType A[],long p,long r)
{//快排序
	long q;
	if(p<r)
	{
		q=Partition(A,p,r);
		QuickSort(A,p,q-1);
		QuickSort(A,q+1,r);
	}
}

long RandomizedPartition(ElemType A[],long p,long r)
{//数组划分随机版本
	long i;
	ElemType temp;
	time_t t;
	srand((unsigned)time(&t));
	i=rand()%(r-p+1)+p;
	temp=A[r];
	A[r]=A[i];
	A[i]=temp;
	return Partition(A,p,r);
}

void RandomizedQuickSort(ElemType A[],long p,long r)
{//快排序随机版本
	long q;
	if(p<r)
	{
		q=RandomizedPartition(A,p,r);
		RandomizedQuickSort(A,p,q-1);
		RandomizedQuickSort(A,q+1,r);
	}
}