爱华网(2011-07-08 14:00:26)转载▼
标签：杂谈
sort()函数与qsort()函数及其头文件
(2010-02-05 19:38:37)
标签：杂谈
分类：计算机基础知识
今天在看程序时，遇见了sort()这个函数，我在网页上搜了一些资料，整合一下
sort()函数是C++中的排序函数其头文件为：#include<algorithm>头文件；qsort()是C中的排序函数，其头文件为：#include<stdlib.h>
先说一下qsort()吧，搜索到的资料容易懂一些。
六类qsort排序方法
qsort函数很好用，但有时不太会用比如按结构体一级排序、二级排序、字符串排序等。
函数原型：void qsort(void *base,size_t nelem,size_t width,int (*fcmp)(const void*,const void *))
输入参数：
base 待排序的数组，nelem 数组元数的个数（长度），width 每一个元素所占存储空间的大小，fcmp 用于对数组元素进行比较的函数的指针（该函数是要自己写的），返回值为1或-1（p1>p2则返回-1，p1<p2则返回1，p1==p2则返回0），size_t是int
输出参数：base 以升序排列
以下是其具体分类及用法(若无具体说明是以降序排列)：
1、对一维数组排序：
（Element_type 是一位数组中存放的数据类型，可以是char,int,float,double,ect）
int comp(const void *p1,const void *p2)
{
return*((Element_type*)p2)>*((Element_type*)p1)?1:-1;
}
int main()
{
Element_type list[MAX];
initial(list);//这是对数组list[max]初始化
qsort(list, sizeof(list),sizeof(Element_type),Comp);//调用函数qsort
return 0;
}
2、对字符串排序：
int Comp(const void *p1,const void *p2)
{
return strcmp((char *)p2,(char *)p1);
}
int main()
{
char a[MAX1][MAX2];
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 ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),Comp);
4、按结构体中多个关键字排序（对结构体多级排序）[以二级为例]：
struct Node
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按y从大到小排序（这是3跟4的区别）
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;
}
sort()函数说起来有一点模糊（没有比较系统的总结）
函数Sort()用于对参数整数数组array的元素进行由小到大的选择排序，其中参数n表示array数组中存储的数组元素数。例如，假设数组array中有10个元素，选择排序就是：先将10个数中的最小数与a[0]对换；再将a[1]到a[9]中的最小数与a[1]对换，….，直到排序完成。
这是我在百度上找到的1011题的答案，我觉得用它来说明sort()函数最具有代表性
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <functional>
using namespace std;
int stick[100], n;
bool used[100];
//unused:没有使用的棍子的数目
//left:剩下的长度
//len:当前认为的计算的长度
bool dfs(int unused, int left, int len)
{
// 所有的棍子已经用了，且没有剩余的长度,符合搜索条件
if (unused == 0 && left == 0)
return true;
int i;
//没有剩下的.则新开一条棍子
if (left == 0)
left = len;
//寻找没有使用过的棍子
for (i=0; i<n; ++i)
{
//找到没有用过的,而且长度比left值要小(能够填进去)
if (!used && stick<=left)
{
//使用当前棍子
used = true;
//若在当前情况下能够扩展出正确答案,则返回
if (dfs(unused-1, left-stick, len))
//成功搜索,返回
return true;
//否则不使用当前的棍子
used = false;
//若使用stick不能扩展出正确结果,那么如果stick与left等长,则证明len不可能是正确答案
//若left与len等长,就是没有办法扩展
if (stick == left || left == len)
break;
}
}
//经过一轮搜索仍得不到正确答案,则返回false
return false;
}
int main()
{
int i, sum;
while (scanf("%d", &n) != EOF && n)
{
sum = 0;
for (i=0; i<n; ++i)
{
scanf("%d", &stick);
used = false;
sum += stick;
}
//先进行从大到小排序
sort(stick, stick+n, greater<int>());
//根据题目条件，从小向大寻找
for (i=stick[0]; i<=sum; ++i)
{
//棍子总长被i整除才进行搜索,否则没用
if (sum % i == 0)
{
if (dfs(n, 0, i))
{
printf("%dn", i);
break;
}
}
}
}
return 0;
}
#include<algorithm>头文件
非修改性序列操作（12个）
循环对序列中的每个元素执行某操作for_each()
查找在序列中找出某个值的第一次出现的位置find()
在序列中找出符合某谓词的第一个元素find_if()
在序列中找出一子序列的最后一次出现的位置find_end()
在序列中找出第一次出现指定值集中之值的位置find_first_of()
在序列中找出相邻的一对值adjacent_find()
计数在序列中统计某个值出现的次数count()
在序列中统计与某谓词匹配的次数count_if()
比较找出两个序列相异的第一个元素
mismatch()两个序列中的对应元素都相同时为真equal()
搜索在序列中找出一子序列的第一次出现的位置search()
在序列中找出一值的连续n次出现的位置search_n()
修改性序列操作（27个）
复制从序列的第一个元素起进行复制copy()
从序列的最后一个元素起进行复制copy_backward()
交换交换两个元素swap()交换指定范围的元素swap_ranges()
交换由迭代器所指的两个元素iter_swap()
变换将某操作应用于指定范围的每个元素transform()
替换用一个给定值替换一些值replace()
替换满足谓词的一些元素replace_if()
复制序列时用一给定值替换元素replace_copy()
复制序列时替换满足谓词的元素replace_copy_if()
填充用一给定值取代所有元素fill()
用一给定值取代前n个元素fill_n()
生成用一操作的结果取代所有元素generate()
用一操作的结果取代前n个元素generate_n()
删除删除具有给定值的元素remove()
删除满足谓词的元素remove_if()
复制序列时删除具有给定值的元素remove_copy()
复制序列时删除满足谓词的元素remove_copy_if()
唯一删除相邻的重复元素unique()
复制序列时删除相邻的重复元素unique_copy()
反转反转元素的次序reverse()
复制序列时反转元素的次序reverse_copy()
环移循环移动元素rotate()
复制序列时循环移动元素rotate_copy()
随机采用均匀分布来随机移动元素random_shuffle()
划分将满足某谓词的元素都放到前面partition()
将满足某谓词的元素都放到前面并维持原顺序stable_partition()
序列排序及相关操作（27个）
排序以很好的平均效率排序sort()
排序，并维持相同元素的原有顺序stable_sort()
将序列的前一部分排好序partial_sort()
复制的同时将序列的前一部分排好序partial_sort_copy()
第n个元素将第n各元素放到它的正确位置nth_element()
二分检索找到大于等于某值的第一次出现lower_bound()
找到大于某值的第一次出现upper_bound()
找到（在不破坏顺序的前提下）可插入给定值的最大范围equal_range()
在有序序列中确定给定元素是否存在binary_search()
归并归并两个有序序列merge()
归并两个接续的有序序列inplace_merge()
有序结构上的集合操作一序列为另一序列的子序列时为真includes()
构造两个集合的有序并集set_union()
构造两个集合的有序交集set_intersection()
构造两个集合的有序差集set_difference()
构造两个集合的有序对称差集（并-交）set_symmetric_difference()
堆操作向堆中加入元素push_heap()
从堆中弹出元素pop_heap()
从序列构造堆make_heap()
给堆排序sort_heap()
最大和最小两个值中较小的min()
两个值中较大的max()
序列中的最小元素min_element()
序列中的最大元素max_element()
词典比较两个序列按字典序的第一个在前lexicographical_compare()
排列生成器按字典序的下一个排列next_permutation()
按字典序的前一个排列prev_permutation()
