qsort() -- 快速排序

beyes

C++ 标准库里的 qsort() 函数是一个基于快速排序算法的排序函数，它可以对一个数组中的内容进行排序，它的原型包含在头文件 <cstdlib> 中，其原型如下：

[C++] 纯文本查看 复制代码

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

函数描述为：对由第一个参数 base 所指向的数组进行排序，第 3 个参数 size 表示该数组的元素的大小，第  2 个参数 num 表示数组的元素个数，第 4 个参数是个函数指针，指向一个自定义函数，该函数会被排序算法所使用。

comparator() 接受两个指针参数，且这两个指针的类型和欲排列数组中的元素类型一致。qsort() 的排序算法正是利用该函数来比较数组中的两个元素，所以在 comparator() 中，我们需要返回两个元素的比较结果：如果相等则返回 0 ，如果第 1 个参数大于第 2 个就返回正数，反之返回负数。


示例1：排序字符串：

[C++] 纯文本查看 复制代码

#include "stdafx.h"
#include <cstdlib>
#include <iostream>
using namespace std;

int comparator(const void *a, const void *b)
{
    return *(char *)a - *(char *)b;
}

int _tmain(int argc, _TCHAR* argv[])
{
    char str[] = "rqfvcdsaewzxtjnbhguyimlkpo";

    qsort(str, strlen(str), 1, comparator);
    cout << "sorted string: " << str << endl;

    return 0;
}

运行输出：

sorted string: abcdefghijklmnopqrstuvwxyz

示例2：排序整数

[C++] 纯文本查看 复制代码

#include "stdafx.h"
#include <cstdlib>
#include <iostream>
using namespace std;

int comparator(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int num[] = {10, 30, 8, 4, 11, 100, 101};
    int i;

    qsort(num, 7, sizeof(int), comparator);
    
    for (i = 0; i < 7; i++)
        cout << num[i] << ' ';

    cout << endl;

    return 0;
}

运行输出：

4 8 10 11 30 100 101

由上可见，原来数组中的内容被排序后的内容所替代。