`
cloudtech
  • 浏览: 4577527 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

C++ qsort 实现

 
阅读更多

自己写的C++ STL Algorithm中qsort的实现如下:

void swap(void *a, void *b, int size)
{
    unsigned char *bytesOfA = reinterpret_cast<unsigned char*>(a);
    unsigned char *bytesOfB = reinterpret_cast<unsigned char*>(b);
    char tmp = 0;
    for(int i = 0; i < size; ++i)
    {
        tmp = *(bytesOfA+i);
        *(bytesOfA+i) = *(bytesOfB+i);
        *(bytesOfB+i) = tmp;
    }
}

int partition(void *base, int num, int size, int (*comparator)(const void *, const void *))
{
    int first = 0, end = num-1;
    while(first < end)
    {
        while(first < end && comparator(base+first*size, base+end*size) <= 0)
        {
            --end;
        }
        if(first < end)
        {
            swap(base+first*size, base+end*size, size);
            ++first;
        }
        while(first < end && comparator(base+first*size, base+end*size) <= 0)
        {
            ++first;
        }
        if(first < end)
        {
            swap(base+first*size, base+end*size, size);
            --end;
        }
    }
    return first;
}

void qsort(void *base, int num, int size, int (*comparator)(const void *, const void *))
{
    if(num > 0)
    {
        int pivot = partition(base, num, size, comparator);
        qsort(base, pivot, size, comparator);
        qsort(base+(pivot+1)*size, num-pivot-1, size, comparator);
    }
}
用poj2388题测试,时间、内存比用STL的qsort还要略少一点,可能是数据不大的原因吧,STL里的qsort可以对非常大的内存空间排序,应该是迭代实现的。

分享到:
评论

相关推荐

    C中的库函数qsort的实现

    C库函数qsort的实现,对学习指针有极大的帮助。可以实现任意类型数据的排序。

    qsort/快速排序C/C++实现

    qsort的具体实现,有注释。 排序函数:int findpivot(int i, int j, int a[]); void swap(int l, int r, int a[]); int partition(int i, int j, int pivot, int a[], int pivotindex); void quicksort(int i, int j...

    快速排序(qsort, quick sort) C语言实现

    鉴于初学C语言或C++时对快速排序算法的了解不够深入,在此上传快速排序的C语言实现代码,该实现代码具有模块化特点,并且在代码中写了注释,并在调试过程中易出错的关键地方做了标注;此外,在代码实现中添加了良好...

    C++自定义结构体排序实现

    C++中自定义结构体选择一个键值 调用sort qsort排序

    C++算法之通用排序

    C++通用排序算法,只需传递比较函数和一些简单的参数就能实现排序,类似API里面的qsort

    二维数组排序

    应用c++库函数 qsort实现二维数组排序,即 举例:排序前:{{1,1,0} {3,0,2}, {1,1,1}, {1,2,0}} 排序后:{{1,1,0}, {1,1,1}, {1,2,0}, {3,0,2}}

    sortProject(Qt5中文排序与英文排序实现).zip

    Qt5自带QCollator和QLocale库,结合qSort()函数,在VS2015开发工具下实现排序,支持中文英文排序,其中中文按照首字母排序,也可以设置按找笔画排序

    QuickSort快速排序的实现

    QuickSort快速排序的...使用C++模版,可实现自定义类型的排序方式 同时通过折半查找检索元素 附带控制台演示 欢迎指正和建议 程序详细描述可见:http://www.zwqxin.com/archives/arithmetic/quick-sort-implement.html

    快排函数的调用qsort();

    快速排序算法通过多次比较和交换来实现排序,其排序流程如下:  (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。...

    Kruskal算法 最小生成树

    这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边(u,v)。 具体实现过程如下: &lt;1&gt; 设一个有n个顶点的连通网络为G(V,E),最初先构造一个只有n个顶点,没有边的非连通图T={V,空},图中...

    Visual C++ 编程资源大全(英文源码 DLL)

    1,01.zip Dialogs in DLL 在DLL中实现对话框(5KB)&lt;END&gt;&lt;br&gt;2,02.zip Export dialogs in MFC Extension DLLs 在MFC扩充DLL中输出对话框(12KB)&lt;END&gt;&lt;br&gt;3,03.zip Remapping resource script ID's ...

    C语言解析教程(原书第4版)(美) 凯利.pdf

    12.3 使用pipe()实现进程间的通信 12.4 信号 12.5 例子:哲学家用餐问题 12.6 矩阵的动态分配 12.6.1 为什么二维数组无法满足要求 12.6.2 用指针数组创建矩阵 12.6.3 调整下标范围 12.6.4 一次分配所有内存 12.7 ...

    C语言FAQ 常见问题列表

    o 3.4 在 C 语言中实现抽象数据类型什么方法最好? o 3.5 在 C 中是否有模拟继承等面向对象程序设计特性的好方法? o 3.6 我遇到这样声明结构的代码: struct name { int namelen; char namestr[1];}; 然后又使用...

    你必须知道的495个C语言问题

    1.8 如何在C中实现不透明(抽象)数据类型? 1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 存储类型 1.10 同一个静态(static)函数或变量的所有声明都必需包含static存储类型...

    《你必须知道的495个C语言问题》

    1.8 如何在C中实现不透明(抽象)数据类型? 5 1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 5 存储类型 6 1.10 同一个静态(static)函数或变量的所有声明都必须包含static...

    你必须知道的495个C语言问题(PDF)

    2.4 在C 语言中实现抽象数据类型什么方法最好? . . . . . . . . . . . 7 2.5 在C 中是否有模拟继承等面向对象程序设计特性的好方法? . . . 7 i 目录ii 2.6 我遇到这样声明结构的代码: struct name f int namelen; ...

Global site tag (gtag.js) - Google Analytics