sort()函数与qsort()函数

编译器函数库自带的快速排序函数。

一、qsort函数

功能：使用快速排序例程进行排序

头文件：stdlib.h

用法： void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));

参数： 1 待排序数组首地址

2 数组中待排序元素数量

3 各元素的占用空间大小

4 指向函数的指针，用于确定排序的顺序

使用qsort()排序并用 bsearch()搜索是一个比较常用的组合，使用方便快捷。

qsort 的函数原型是void __cdecl qsort (void *base,size_tnum,size_t width,int (__cdecl *comp)(const void *,const void*))

其中base是排序的一个集合数组，num是这个数组元素的个数，width是一个元素的大小，comp是一个比较函数。

比如：对一个长为1000的数组进行排序时，int a[1000]; 那么base应为a，num应为 1000，width应为 sizeof(int)，comp函数随自己的命名。

qsort(a,1000,sizeof(int),comp);

其中comp函数应写为：

qsort六类排序方法：

1、对int类型数组排序

1 int num[100];
2 
3 int cmp ( const void *a , const void *b )
4 {
5     return *(int *)a - *(int *)b;
6 }
7 
8 qsort(num,100,sizeof(num[0]),cmp);

View Code

2、对char类型数组排序（同int类型）

1 char word[100];
2 
3 int cmp( const void *a , const void *b )
4 {
5     return *(char *)a - *(char *)b;
6 }
7 
8 qsort(word,100,sizeof(word[0]),cmp);

View Code

3、对double类型数组排序

1 double in[100];
2 
3 int cmp( const void *a , const void *b )
4 {
5     return *(double *)a > *(double *)b ? 1 : -1;
6 }
7 
8 qsort(in,100,sizeof(in[0]),cmp);

View Code

4、对结构体一级排序

 1 struct Sample
 2 {
 3     double data;
 4     int other;
 5 }s[100]
 6 
 7 //按照data的值从小到大将结构体排序
 8 
 9 int cmp( const void *a ,const void *b)
10 {
11     return (*(struct Sample 
12 *)a).data > (*(struct Sample 
13 *)b).data ? 1 : -1;
14 }
15 
16 qsort(s,100,sizeof(s[0]),cmp);

View Code

5、对结构体二级排序

 1 struct Sample
 2 {
 3    int x;
 4    int y;
 5 }s[100];
 6 
 7 //按照x从小到大排序，当x相等时按照y从大到小排序
 8 
 9 int cmp( const void *a , const void *b )
10 {
11          struct Sample *c = (struct Sample 
12 *)a;
13          struct Sample *d = (struct Sample 
14 *)b;
15          if(c->x != d->x)   return c->x - d->x;
16          else               return d->y - c->y;
17 }
18 
19 qsort(s,100,sizeof(s[0]),cmp);

View Code

6、对字符串进行排序

 1 struct Sample
 2 {
 3    int data;
 4    char str[100];
 5 }s[100];
 6 
 7 //按照结构体中字符串str的字典顺序排序
 8 
 9 int cmp ( const void *a , const void *b )
10 {
11     return strcmp( (*(struct Sample 
12 *)a).str , (*(struct Sample 
13 *)b).str );
14 }
15 
16 qsort(s,100,sizeof(s[0]),cmp);

View Code

举例：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 char s[2001][1001];
 6 
 7 int cmp(const void *a, const void *b)
 8 {
 9      return strcmp((char *)a,(char *)b);
10 }
11 
12 int main()
13 {
14     int i,n;
15     scanf("%d",&n);
16     getchar();
17     for(i=0;i<n;i++) 
18           gets(s[i]);
19     qsort(s,n,1001*sizeof(char),cmp);
20     for(i=0;i<n;i++) 
21           puts(s[i]);
22     return 0;
23 }

qsort举例（字符串二维数组）

二、sort函数

sort()函数是C++中的排序函数其头文件为：#include<algorithm>头文件；

sort与stable_sort

这两个函数的原理都是快速排序，时间复杂度在所有排序中最低，为O(nlog2n) ;

sort的应用；

1、可以传入两个参数；

sort(a,a+N) ,其中a是数组，a+N表示对a[0]至a[N-1]的N个数进行排序(默认从小到大排序)；

2、传入三个参数；

sort(a,a+N,cmp),第三个参数是一个函数；

如果让函数从大到小排序，可以用如下算法实现；

bool cmp(int a,int b){return a>b};

sort(A,A+N,cmp);

而stable_sort的用法与sort一致，区别是stable_sort函数遇到两个数相等时，不对其交换顺序；这个应用在数组里面不受影响，当函数参数传入的是结构体时，会发现两者之间的明显区别；

举例：

#include <iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int i,n,A[100];
    cin>>n;
    for(i=0;i<n;i++)
        cin>>A[i];

    sort(A,A+n,cmp);

    for(i=0;i<n;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}

sort