关于qsort的系统调用共有七种用法,详细介绍在这里http://apps.hi.baidu.com/share/detail/2056555.这里讨论的是最一般的对一维整数型数组排序情况: 1.qsort 是C的排序函数,(在VC 6.0中使用当然OK),其头文件是#include<stdlib>. 自定义函数cmp仅针对一维整数型数组,定义如下: int cmp(const void *a,const void *b) { return (*(int*)a-*(int*)b); } 对应qsort: qsort(p,num,sizeof(p[0]),cmp); 2.sort 是C++的排序函数,其头文件是#include<algorithm> 自定义函数cmp仅针对一维整数型数组,定义如下: bool cmp(int a,int b) { return a<b; } //注意两者的返回值类型!!! 对应sort: sort(p,p+num,cmp); 主要部分就是这些,算了,把鸡肋也给出来好了.. .. int main() { int num; cout<<"Please input the size of your array.."<<endl; cin>>num; int *p =new int[num]; for(int i = 0;i != num;i++) cin>>p[i]; // qsort(p,num,sizeof(p[0]),cmp); sort(p,p+num,cmp); for(int j = 0;j != num;j++) cout<<p[j]<<' '; cout<<endl; delete p; return 0; } 转帖部分: 关于快排的一些小问题 1.快排的复杂度,当元素个数比较少时(10^2的数量级左右),快排的速度跟冒泡相比并没有快很多,还有如果要排序的元素大部分都已经是排好顺序了时,快排效率会下降,但是其最坏情况是N^2(当元素全部是已经排好的顺序时),一般情况(也即平均效率)是N*Log2(N),最好情况是N(当元素全部是逆序时),快排的特点是元素越乱排序速度越快,所以可以看出,虽然元素少时使用快排并没有很大优势,但是在快排的最坏情况跟冒泡、选择排序(冒泡、选择排序其复杂度不受元素顺序影响,永远为N^2)一样,所以快排永远是最快的。 2.快排是不稳定的,这里的稳定性是指对于相同元素的处理上,快排会打乱相同元素的先后顺序(原因就在于快排排序原理,其排序过程是不断把元素分组打乱进行的),当然如果单纯排序一列数字是没什么区别的,假设我们有这样一列数字3,3,3,但是三个3是有区别的,我们标记为3a,3b,3c,快排后的结果不一定就是3a,3b,3c这样的排列,所以在某些特定场合我们要用结构体来使其稳定(No.5的例子就是说明这个问题的) |
|
来自: 昵称14216904 > 《待分类》