快速排序代码,C代码库,德仔网

代码语言
代码分类
【C】快速排序
作者:麦田里的守护者 / 发布于2013/6/4/ 684

	//作者：石金南
	//功能：快速排序
	//日期：2013.05.28
	#include<stdio.h>
	#include<math.h>
	#include<stdlib.h>
	#include<time.h>
	#define num 100//随机生成num个数进行排序

	typedef struct
	{
	int *n;
	int length;
	}SSTable;
	SSTable *Creat(int n);//构造一个含有n个元素的顺序表
	int paixu(int n[],int low,int high);//对顺序表进行排序
	void print(SSTable *ST);//显示顺序表
	void Time();//显示系统时间
	void pai(int n[]);//插入排序
	void Destroy(SSTable *p);//销毁顺序表
	int FindNum(SSTable *ST,int Dk);//寻找Dk在顺序表中的什么位置
	void InsertNum(SSTable *ST,int e,int i);//在顺序表中插入元素e,与第i个元素开始比较
	int main()
	{
	SSTable *ST;
	int Dk,i;
	ST=Creat(num);
	Time();
	paixu(ST->n,0,num-1);//排序
	Time();
	while(1)
	{
	 printf("排序好的顺序表：");
	 print(ST);
	 printf("输入要找的元素Dk:");
	scanf("%d",&Dk);
	i=FindNum(ST,Dk);
	if(ST->n[i]==Dk)printf("位置为：%d %d",i,ST->n[i]);
	else InsertNum(ST,Dk,i); }
	Destroy(ST);
	getchar();
	system("pause");

	return 0;
	}
	SSTable *Creat(int nu)//建立顺序表,系统随机生成顺序表的数
	{
	SSTable *ST;
	ST=(SSTable*)malloc(sizeof(SSTable));
	ST->n=(int *)malloc(nu*sizeof(int));//开劈空间
	ST->length=nu;
	int i;
	srand((unsigned long)time(0));//生成种子
	for(i=0;i<nu;i++)
	 ST->n[i]=rand();//生成随机数
	return ST;
	}
	int FindNum(SSTable *ST,int Dk)//查询
	{
	int m,n,i;
	n=0;
	m=ST->length-1;
	if(Dk>=ST->n[m])i=m;
	else for(;n!=m;)//以二分法查找
	{
	 if(i==((n+m)/2))
	 {if(ST->n[i]<Dk)i++;
	 break;}
	 i=(n+m)/2;
	 if(ST->n[i]==Dk)return i;
	 else if(ST->n[i]>Dk)
	 {
	 m=i;
	 }
	 else n=i;
	}
	if(ST->n[m]==Dk)return i;//返回下标
	printf("顺序表中没有此元素,在顺序表中插入此函数\n");return i;
	}
	void InsertNum(SSTable *ST,int e,int i)//在顺序表中插入元素e，与第i个元素开始比较
	{
	int m;
	ST->n=(int*)realloc(ST->n,(ST->length+1)*sizeof(int));
	if(!ST->n)exit(0);//存储空间分配失败
	ST->length+=1;
	if(ST->n[i]<=e)
	{
	 for(m=ST->length-1;m-1>i;m--)ST->n[m]=ST->n[m-1];
	 ST->n[m]=e;
	}
	else
	{
	 for(m=ST->length-1;m>i;m--)ST->n[m]=ST->n[m-1];
	 ST->n[m]=e;
	}
	}

	
	void Destroy(SSTable *p)//销毁顺序表
	{
	free(p->n);//销毁顺序表中的元素空间
	free(p);//销毁顺序表
	}
	void Time()//显示系统时间
	{
	struct tm *local;
	 time_t t;
	t=time(NULL);
	 local=localtime(&t);
	 printf("local time and date:%s\n",asctime(local));
	}
	void pai(int n[])//插入排序
	{
	int i=0,j=0,m=0,y;
	for(;i<num;i++)
	{
	 j=i+1;
	 for(;n[j]>n[m];m++);
	 y=n[m];
	 n[m]=n[j];
	 for(;(j-1)>m;j--)
	 {
	 n[j]=n[j-1];
	 }
	 n[j]=y;
	 m=0;
	}
	}


	int paixu(int n[],int low,int high)//
	{
	int key=n[low],m1,m2,i=0,j=0,x,y;//第一个元素为哨兵
	m1=low; m2=high;//保护好初末元素的下标
	//仅当区间长度大于1才进行排序
	if(low<high)
	{
	 while(low<high)//
	 {
	 i=low;j=high;
	 for(;n[high]>key&&high>low;high--);
	 if(low<high){x=n[high];
	 n[high]=n[low];
	 n[low]=x;low++;}
	 for(;n[low]<key&&i<high;low++);
	 if(low<high){ y=n[low];
	 n[low]=n[high];
	 n[high]=y;high--;}
	 }
	 paixu(n,m1,high-1);//小于key的左边排列
	 paixu(n,low+1,m2);//大于的key右边排列
	}return 0;
	}
	void print(SSTable *ST)//输出顺序表
	{
	for(int i=0;i<ST->length;i++)
	 printf("%d ",ST->n[i]);
	printf("\n");
	}
试试其它关键字
　快速排序　
同语言下
可能有用的
麦田里的守护者贡献的其它代码(2)