（排序算法）调用系统快排qsort

调用形式：qsort(arr,nelem,size,cmp)

arr—待排序数组首地址

nelem—待排序的数组元素的个数

size—数组单个元素占用空间大小，sizeof(数组元素类型)

cmp—比较函数，确定排序要求，是升序还是降序

主要任务是自己定义一个cmp函数，其余排序工作交给神奇的qsort

下面介绍几个例子

1、对整型数组排序int

int arr[100];

int cmp(const void* a,const void* b)

{

    return *(int*)a - *(int*)b;    //升序排序，如果换成return *(int*)b - *(int*)a的话，则是降序排序

}

qsort(arr,100,sizeof(int),cmp);

对double型和char型的数组类似上面int型的数组

2、对字符串数组的排序char arr[]

char arr[100][100];

int cmp(const void* a,const void* b)

{

     return strcmp((char*)a,(char*)b);

}

qsort(arr,n,sizeof(arr[0]),cmp);

3、对指针数组排序 char*

#include<iostream>
using namespace std;
int cmp(const void* a,const void* b)
{
    return strcmp(*((char**)a),*((char**)b));
}
int main()
{
    char *arr[100];
    int n;
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        arr[i] = new char[100];
        cin>>arr[i];
    }
    qsort(arr,n,sizeof(char*),cmp);
    for(int i = 0;i<n;i++)
    {
        cout<<arr[i]<<endl;
    }
}

4、对结构数组排序

#include<iostream>
using namespace std;

struct infor
{
    int id;
    char* name;
};
int cmp(const void* a,const void* b)
{
    return (*((infor*)a)).id-(*((infor*)b)).id;   //或者return ((infor*)a)->id-((infor*)b)->id;
}
int main()
{
    int n;
    cin>>n;
    infor * arr;
    arr = new infor[n];
    for(int i = 0;i<n;i++)
    {
        cin>>arr[i].id;
        arr[i].name = new char[100];
        cin>>arr[i].name;
    }
    qsort(arr,n,sizeof(infor),cmp);
    for(int i = 0;i<n;i++)
    {
        cout<<arr[i].id<<"  "<<arr[i].name<<endl;
    }
}

5、对结构数组排序补充

在4中，如果是id相同的情况下，可以按照name的大小来排序，则cmp函数改下如下：

int cmp(const void* a,const void* b)
{
    if( ((infor*)a)->id!=((infor*)b)->id)
        return ((infor*)a)->id-((infor*)b)->id;
    else return strcmp(((infor*)a)->name,((infor*)b)->name);
}

总之，记住cmp函数的写法就可以了，对于两个void* 的指针a,b，首先将a(或者b)强制类型转换成待排序数组的类型的指针，例如：

如果数组元素是int，就强制转换成int*；

如果数组元素是char*，就强制类型转换成char**；

如果数组元素类型是char[]，就强制类型转换成char*；

如果数组元素类型是struct infor，就强制类型转换成infor*；

等等…

然后再把强制转换后的指针取内容，用*符号，得到我们待排序数组的元素类型的数，例如：

*((int*)a)，(int*)a取内容后得到int类型的数，说明数组元素类型是int arr[]

*((char**)a)，(char**)a取内容后得到char*类型的数，说明数组元素类型是char* arr[]

特别的，当数组元素类型是char[]时，比如char arr[100][100]，不需要取内容，因为可以直接可以用指针char*访问数组元素

另外对于结构型的数组元素，我们需要用什么数做比较(比如id还是name)，就设法通过强制类型转换得到的指针(infor*)a得到这个数

比如可以这样，((infor*)a)->id，不用*取内容，直接用指针得到id；也可以这样，(*((infor*)a)).id

通过以上方法得到我们需要比较的数，再比较两个数的大小，返回比较的值就完成了cmp函数。

（排序算法）调用系统快排qsort,布布扣,bubuko.com

（排序算法）调用系统快排qsort

原文：http://www.cnblogs.com/fishsorry/p/3574542.html