突然发现，自己系统的qsort调用的很溜，可是却连个qsort怎么实现的都不知道。。。实在惭愧。。。于是从新学习排序，然后用c语言写了个比较简陋的qsort
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include<stdio.h> struct man{ int len; char name[100]; }; typedef struct man mtype; mtype s[100]; int cmp(const void *a, const void *b) { return ((mtype*)a)->len-((mtype*)b)->len; } int split(int low, int high,mtype *a,int (*cmp)(const void *a,const void *b)) { mtype t; t=a[low]; while(low<high) { while(cmp(&a[high],&t)>0&&low<high) high--; if(low==high) break; else { a[low]=a[high]; low++; } //将比t小的数都放到t的前面 while(cmp(&a[low],&t)<=0&&low<high) low++; if(low==high) break; else { a[high]=a[low]; high--; //比t大的放后面 } } a[low]=t; return low; } void qsort(mtype *a,int low,int high,int (*cmp)(const void *a,const void *b)) { int p; if(low<high) { p=split(low,high,a,cmp);//取一个数进行分割 qsort(a,low,p-1,cmp);//前部分迭代 qsort(a,p+1,high,cmp);//后部分迭代 } } int main() { int a,b,i; while(scanf("%d",&b)!=EOF) { for(i=0;i<b;i++) { scanf("%d %s",&s[i].len,s[i].name); } qsort(s,0,b-1,cmp); for( i=0;i<b;i++) { printf("%s ",s[i].name); } printf("\n"); } } |
这个qsort就是nlogn的复杂度，没有进行任何优化
每次选第一个数作为分割标准
但是已经够用了。。。
