首页 > 代码库 > 自己写快排模板与C++快排库函数使用
自己写快排模板与C++快排库函数使用
自己写快排模板与C++快排库函数使用
1、自己写快排模板
我理解的快速排序思想原理是：
假定待排序数组的范围是0~N
1、在一个数组中找一个数作为中心点M(可以使用固定位置的数，也可以随机的采用数组中的数)
2、把数组中所有的数与这个中心点进行比较。小于中心点的数移到中心点左边，大于中心点的数移到中心点右边。
3、经过上面两步可以得到由M点所划分的两个数组(一个数组都小于等于M，一个都大于等于M),再对这两个数组递归的进行1、2所示步骤，知道划分的数组大小为0；
快排思想实现的主要的重点难点在于第2步的实现：
1、中心点取在左边,所以重右边J的位置开始判断，I目前的值为Left
2、如果J>=M(中心点的值这里为BASE_Num),则J往左移，反之如果J<M则将数组下标为I的数赋值为J，然后进行第3步
3、I移到下一个位置，如果数组Array[I]的值小于等于M，则I继续往右移，直到Array[i]>M，将Array[J]的值赋为Array[I]
4、重复3、4步 直到I>J
可能我自己的表达不是很清楚，大概的思路和实现就是这样了，可以参考以下文章和代码进行理解。
http://blog.csdn.net/morewindows/article/details/6684558
九度OJ 1196成绩排序 地址：http://ac.jobdu.com/problem.php?pid=1196
#include <stdio.h>
typedef struct
{
int num;
int grade;
}STUDENT_INFO_T;
STUDENT_INFO_T student[101];
//声明一个COMP类型函数指针 以后就可以直接用COMP定义该函数指针
typedef int (*COMP)(const STUDENT_INFO_T *, const STUDENT_INFO_T *);
//比较函数a大于b(a在b后面) 返回1 否则返回0
int qCompare(const STUDENT_INFO_T *a, const STUDENT_INFO_T *b)
{
if(a->grade == b->grade)
{
return (a->num - b->num)>0?(1):(0);
}
else
{
return (a->grade - b->grade)>0?(1):(0);
}
}
//快排函数模板
void quick_sort(STUDENT_INFO_T *p, int l, int r, COMP Comp)
{
if(l < r)
{
int i=l, j=r;
STUDENT_INFO_T Base_num = p[l];
while(i < j)
{
while(i<j && Comp(&p[j],&Base_num)) //pj large than px
j--;
if(i < j)
{
p[i++] = p[j];
}
while(i<j && !Comp(&p[i],&Base_num)) //pi small than px
i++;
if(i < j)
{
p[j--] = p[i];
}
}
p[i] = Base_num;
quick_sort(p, l, i-1 , Comp);
quick_sort(p, i+1 , r, Comp);
}
}
int main(int argc, char **argv)
{
int student_count;
int i;
while(scanf("%d",&student_count)!=EOF)
{
for(i=0; i<student_count; i++)
{
scanf("%d %d",&student[i].num,&student[i].grade);
}
quick_sort(student, 0, student_count-1, qCompare);
for(i=0; i<student_count; i++)
{
printf("%d %d\n",student[i].num,student[i].grade);
}
}
return (0);
} 九度OJ 1061成绩排序 地址:http://ac.jobdu.com/problem.php?pid=1061
#include <stdio.h>
typedef struct
{
char name[101];
int age;
int grade;
}STUDENT_INFO_T;
STUDENT_INFO_T student[1001];
//声明一个COMP类型函数指针 以后就可以直接用COMP定义该函数指针
typedef int (*COMP)(const STUDENT_INFO_T *, const STUDENT_INFO_T *);
//与strcmp函数功能一致
int my_strcmp(const char *str1, const char *str2)
{
while(*str1 == *str2)
{
if(*str1 == '\0')
return (0);
str1++;
str2++;
}
return (*str1 - *str2);
}
//比较函数a大于b(a在b后面) 返回1 否则返回0
int qCompare(const STUDENT_INFO_T *a, const STUDENT_INFO_T *b)
{
if(a->grade == b->grade)
{
if(my_strcmp(a->name,b->name) == 0)
{
return (a->age - b->age)>0?(1):(0);
}
else
{
return my_strcmp(a->name,b->name)>0?(1):(0);
}
}
else
{
return (a->grade - b->grade)>0?(1):(0);
}
}
//快排函数模板
void quick_sort(STUDENT_INFO_T *p, int l, int r, COMP Comp)
{
if(l < r)
{
int i=l, j=r;
STUDENT_INFO_T Base_num = p[l];
while(i < j)
{
while(i<j && Comp(&p[j],&Base_num)) //pj large than px
j--;
if(i < j)
{
p[i++] = p[j];
}
while(i<j && !Comp(&p[i],&Base_num)) //pi small than px
i++;
if(i < j)
{
p[j--] = p[i];
}
}
p[i] = Base_num;
quick_sort(p, l, i-1 , Comp);
quick_sort(p, i+1 , r, Comp);
}
}
int main(int argc, char **argv)
{
int student_count;
int i;
while(scanf("%d",&student_count)!=EOF)
{
for(i=0; i<student_count; i++)
{
scanf("%s %d %d",student[i].name,&student[i].age,&student[i].grade);
}
quick_sort(student, 0, student_count-1, qCompare);
for(i=0; i<student_count; i++)
{
printf("%s %d %d\n",student[i].name,student[i].age,student[i].grade);
}
}
return (0);
} 2、C++ 快排库函数使用（特殊情况使用自定义比较函数）
C/C++中有一个快速排序的标准库函数qsort ，在stdlib.h 中声明，其原型为：
void qsort(void *base, int nelem, unsigned int width, int ( * pfCompare)( const void *, const void*));
base 是待排序数组的起始地址
nelem 是待排序数组的元素个数
width 是待排序数组的每个元素的大小（以字节为单位）
pfCompare 是一个函数指针，它指向一个“比较函数”。
qsort 函数的用法规定，“比较函数”的原型应是：
int FunctionName(const void * elem1, const void * elem2);
elem1 和elem，指向待比较的两个元素。
* elem1 和* elem2 就是待比较的两个元素。
该函数必须具有以下行为：
1) 如果 * elem1 应该排在 * elem2 前面，则函数返回值是负整数（任何负整数都行）。
2) 如果 * elem1 和* elem2 哪个排在前面都行，那么函数返回0
3) 如果 * elem1 应该排在 * elem2 后面，则函数返回值是正整数（任何正整数都行）。
1) 关键的函数库：
#include <stdlib.h>
2) 关键的比较函数（以下为一个简单的例子）：
int Comp(const void *p1,const void *p2)
{
return ( *((int*)p1) )-( *((int*)p2) );}
3) 关键的调用函数库---快速排序：
qsort(nums,MAX_NUM,sizeof(int),Comp);
下面为各种特殊情况下的比较函数模板：
1)对一维数组排序:
(Element_type是一位数组中存放的数据类型，可以是char, int, float, double, etc)
int Comp(const void *p1,const void *p2 )
{
return *((Element_type *)p2)-*((Element_type *)p1);
}
int main()
{
Element_type list[MAX];
initial(list);
qsort(list, sizeof(list)/sizeof(Element_type),sizeof(Element_type),Comp);
//或者qsort(list, MAX,sizeof(Element_type),Comp);
return 0;
}2)对字符串排序:
int Comp(const void *p1,const void *p2)
{
return strcmp((char *)p2),(char *)p1);
}
int main()
{
char a[MAX1][MAX2]; //这里我用动态数组 char =new 。。。不行
initial(a);
qsort(a,lenth,sizeof(a[0]),Comp); //lenth 为数组a的长度
}3)按结构体中某个关键字排序(对结构体一级排序):
struct Node
{
double data;
int other;
}s[100];
int Comp(const void *p1,const void *p2)
{
return (*(Node *)p2)->data-(*（Node *）p1)->data;
}
qsort(s,100,sizeof(s[0]),Comp);4)按结构体中多个关键字排序(对结构体多级排序)[以二级为例]:
struct Node
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按y从大到小排序
int Comp(const void *p1,const void *p2)
{
struct Node *c = (Node *)p1;
struct Node *d = (Node *)p2;
if(c->x != d->x) return c->x-d->x;
else return d->y - c->y;
}5)对结构体中字符串进行排序:
struct Node
{
int data;
char str[100];
}s[100];
//按照结构体中字符串 str 的字典序排序
int Comp(const void *p1,const void *p2)
{
return strcmp((*(Node *)p1)->str,(*(Node *)p2)->str);
}
qsort(s,100,sizeof(s[0],Comp);6)计算几何中求凸包的Comp:
//以下是我从别人那儿抄来的，暂时还没用过
int Comp(const void *p1,const void *p2) //重点Comp函数，把除了1点外的所有的点旋转角度排序
{
struct point *c=(point *)p1;
struct point *d=(point *)p2;
if( cacl(*c, *d,p[1]) < 0)
return 1;
else if(!cacl(*c, *d, p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y )) //如果在一条直线上，则把远的放在前面
return 1;
else
return -1;
}示例代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct data
{
int num;
char name[9];
int grade;
}student[100009];
int CompNum(const void *c,const void *d)
{
return (*(data *)c).num-(*(data *)d).num;
}
int CompName(const void *p1,const void *p2)
{
struct data *c=(data *)p1;
struct data *d=(data *)p2;
if(strcmp((*(data *)c).name,(*(data *)d).name)!=0)
return strcmp((*(data *)c).name,(*(data *)d).name); //注意括号
else
return (*(data *)c).num-(*(data *)d).num;
}
int CompGrade(const void *p1,const void *p2)
{
struct data *c=(data *)p1;
struct data *d=(data *)p2;
if((*(data *)c).grade!=(*(data *)d).grade)
return (*(data *)c).grade-(*(data *)d).grade;
else
return (*(data *)c).num-(*(data *)d).num;
}
void Print(struct data student1[],int x)
{
for(int i=0;i<x;i++)
printf("%06d %s %d\n",student1[i].num,student1[i].name,student1[i].grade);
}
void NumOrder(struct data student2[],int n)
{
qsort(student,n,sizeof(student[0]),CompNum);
Print(student,n);
}
void NameOrder(struct data student2[],int n)
{
qsort(student,n,sizeof(student[0]),CompName);
Print(student,n);
}
void GradeOrder(struct data student2[],int n)
{
qsort(student,n,sizeof(student[0]),CompGrade);
Print(student,n);
}
int main()
{
int n,c,count=1;
while(scanf("%d%d",&n,&c)==2&&n)
{
for(int i=0;i<n;i++)
scanf("%d %s %d",&student[i].num,&student[i].name,&student[i].grade);
printf("Case %d:\n",count++);
if(c==1)
NumOrder(student,n);
else if(c==2)
NameOrder(student,n);
else if(c==3)
GradeOrder(student,n);
//for( i=0;i<n;i++)
// printf("%06d %s %d\n",student[i].num,student[i].name,student[i].grade);
}
return 0;
}自己写快排模板与C++快排库函数使用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。