自己写的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的实现,对学习指针有极大的帮助。可以实现任意类型数据的排序。
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...
鉴于初学C语言或C++时对快速排序算法的了解不够深入,在此上传快速排序的C语言实现代码,该实现代码具有模块化特点,并且在代码中写了注释,并在调试过程中易出错的关键地方做了标注;此外,在代码实现中添加了良好...
C++中自定义结构体选择一个键值 调用sort qsort排序
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}}
Qt5自带QCollator和QLocale库,结合qSort()函数,在VS2015开发工具下实现排序,支持中文英文排序,其中中文按照首字母排序,也可以设置按找笔画排序
QuickSort快速排序的...使用C++模版,可实现自定义类型的排序方式 同时通过折半查找检索元素 附带控制台演示 欢迎指正和建议 程序详细描述可见:http://www.zwqxin.com/archives/arithmetic/quick-sort-implement.html
快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。...
这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边(u,v)。 具体实现过程如下: <1> 设一个有n个顶点的连通网络为G(V,E),最初先构造一个只有n个顶点,没有边的非连通图T={V,空},图中...
1,01.zip Dialogs in DLL 在DLL中实现对话框(5KB)<END><br>2,02.zip Export dialogs in MFC Extension DLLs 在MFC扩充DLL中输出对话框(12KB)<END><br>3,03.zip Remapping resource script ID's ...
12.3 使用pipe()实现进程间的通信 12.4 信号 12.5 例子:哲学家用餐问题 12.6 矩阵的动态分配 12.6.1 为什么二维数组无法满足要求 12.6.2 用指针数组创建矩阵 12.6.3 调整下标范围 12.6.4 一次分配所有内存 12.7 ...
o 3.4 在 C 语言中实现抽象数据类型什么方法最好? o 3.5 在 C 中是否有模拟继承等面向对象程序设计特性的好方法? o 3.6 我遇到这样声明结构的代码: struct name { int namelen; char namestr[1];}; 然后又使用...
1.8 如何在C中实现不透明(抽象)数据类型? 1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 存储类型 1.10 同一个静态(static)函数或变量的所有声明都必需包含static存储类型...
1.8 如何在C中实现不透明(抽象)数据类型? 5 1.9 如何生成“半全局变量”,就是那种只能被部分源文件中的部分函数访问的变量? 5 存储类型 6 1.10 同一个静态(static)函数或变量的所有声明都必须包含static...
2.4 在C 语言中实现抽象数据类型什么方法最好? . . . . . . . . . . . 7 2.5 在C 中是否有模拟继承等面向对象程序设计特性的好方法? . . . 7 i 目录ii 2.6 我遇到这样声明结构的代码: struct name f int namelen; ...