曲径通幽论坛

标题: qsort() -- 快速排序 [打印本页]

---

作者: beyes    时间: 2011-12-8 09:45
标题: qsort() -- 快速排序
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 << ' ';



    cout << endl;



    return 0;

}

运行输出：

4 8 10 11 30 100 101

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

---

欢迎光临 曲径通幽论坛 (http://www.groad.net/bbs/)

Powered by Discuz! X3.2