qsort（基本快速排序的方法，每次把数组分成两部分和中间的一个划分值，而对于有多个重复值
的数组来说，基本快速排序的效率较低，且不稳定）。集成在C语言库函数里面的的qsort函数，
使用三路划分的方法解决排序这个问题。所谓三路划分，是指把数组划分成小于划分值，等于
划分值和大于划分值的三个部分。
具体介绍：-^^
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )
int compare (const void *elem1, const void *elem2 ) );
qsort（即，quicksort）主要根据你给的比较条件给一个快速排序，主要是通过指针移动实现排序
功能。排序之后的结果仍然放在原来数组中。
参数意义如下:
第一个参数 base 是需要排序的目标数组名（或者也可以理解成开始排序的地址，因为可以写
&s[i]这样的表达式）
第二个参数 num 是参与排序的目标数组元素个数
第三个参数 width 是单个元素的大小（或者目标数组中每一个元素长度），推荐使用sizeof(s[0]）
这样的表达式
第四个参数 compare 就是让很多人觉得非常困惑的比较函数啦。
我们来简单讨论compare这个比较函数（写成compare是我的个人喜好，你可以随便写成什么，比如 cmp 什么的，在后面我会一直用cmp做解释）。
典型的compare的定义是int compare(const void *a,const void *b);
返回值必须是int，两个参数的类型必须都是const void *，那个a,b是随便写的，个人喜好。假
设是对int排序的话，如果是升序，那么就是如果a比b大返回一个正值，小则负值，相等返回0，其他的依次类推，后面有例子来说明对不同的类型如何进行排序。
qsort 的使用方法：
一、对int类型数组排序
int num[100];
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b; //升序排序
//return *(int *)b - *(int *)a; //降序排序
/*可见：参数列表是两个空指针，现在他要去指向你的数组元素。所以转型为你当前的类型，然后取值。
升序排列时，若第一个参数指针指向的“值”大于第二个参数指针指向的“值”，则返回正；若第一个参数指针指向的“值”等于第二个参数指针指向的“值”，则返回零；若第一个参数指针指向的“值”小于第二个参数指针指向的“值”，则返回负。
降序排列时，则刚好相反。
*/
}
qsort(s,n,sizeof(s[0]),cmp);
示例完整函数（已在 VC6.0上运行通过）：
#include
#include
#include
int s[10000],n,i;
int cmp(const void *a,const void *b)
{
return(*(int *)b-*(int *)a); //实现的是升序排序
}
int main()
// 输入想要输入的数的个数
scanf("%d",&n);
for(i=0;i scanf("%d",&s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i printf("%d ",s[i]); return(0); } 二、对char类型数组排序（同int类型） char word[100]; int cmp( const void *a , const void *b ) { //注意，网上很多版本是“ return *(char *)a - *(int *)b; ” //因为编辑者的不用心，盲目copy，以讹传讹，传的一直是错的 *(int *)b //应该是return *(char *)a - *(char *)b; return *(char *)a - *(char *)b; } qsort(word,100,sizeof(word[0]),cmp); //附，可能 getchar(); 会派上用场 三、对double类型数组排序（特别要注意） double in[100]; int cmp( const void *a , const void *b ) { return *(double *)a > *(double *)b ? 1 : -1; //返回值的问题，显然cmp返回的是一个整型，所以避免double返回小数而被丢失，用一个判断返回值。 } qsort(in,100,sizeof(in[0]),cmp); //附：排序结果的输出，一般建议用“ %g ” 格式 /* 在这里多嘴一句，"%g"格式输出虽然书上是说系统会自动选择 " %f " 格式和 " %e " 格式中长度较短的格式，并去掉无意义的0，但实际上系统如果选择了" %e "，系统会输出比“ %e " 格式更省一位的格式输出。（此结论，来自VC6.0的实际操作）*/ 四、对结构体一级排序 struct In { double data; int other; }s[100] //按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写 int cmp( const void *a ,const void *b) { return (*(In *)a).data > (*(In *)b).data ? 1 : -1; //注意，这条语句在VC6.0环境下运行可能会出错，但是并不是语句错了，而是你要先 Build ，或者全部重建。总之语句是对的。 //或者你可以将这上面1条语句改成下面这3条语句 //struct In *aa = (In *)a; //struct In *bb = (In *)b; //return aa->data > bb->data ? 1 : -1; } qsort(s,100,sizeof(s[0]),cmp); 五、对结构体二级排序 struct In { int x; //你可以比喻成：失败次数 int y; //你可以比喻成：成功次数 }s[100]; //按照x从小到大排序，当x相等时按照y从大到小排序。你可以想象成：失败是主要因素的一个问题，先比较失败次数少，失败次数相同再看成功次数多。 int cmp( const void *a , const void *b ) { struct In *c = (In *)a; struct In *d = (In *)b; if(c->x != d->x) return c->x - d->x; else return d->y - c->y; } qsort(s,100,sizeof(s[0]),cmp); 六、对字符串进行排序 struct In { int data; char str[100]; }s[100]; //按照结构体中字符串str的字典顺序排序 int cmp ( const void *a , const void *b ) { return strcmp( (*(In *)a)->str , (*(In *)b)->str ); } qsort(s,100,sizeof(s[0]),cmp); 注意！qsort 中的 cmp 得自己写。 再说说 sort （常用于 C++ ） sort 使用时得注明：using namespace std; 或直接打 std::sort() 还得加上 #include 例： #include #include using namespace std; int main() { int a[20]; for(int i=0;i<20;++i) cin>>a[i]; sort(a,a+20); //范围，很明显这里是a+20 注意，这是必要的，如果是a+19 for(i=0;i<20;i++) //最后一个值a[19]就不会参与排序。 cout< return 0; } std::sort是一个改进版的qsort. std::sort函数优于qsort的一些特点：对大数组采取9项取样，更完全的三路划分算法，更细致的对不同数组大小采用不同方法排序。 最后，我们来说说sort、qsort的区别： sort是qsort的升级版，如果能用sort尽量用sort，使用也比较简单，不像qsort还得自己去写cmp 函数，只要注明使用的库函数就可以使用，参数只有两个（如果是普通用法）头指针和尾指针； 默认sort排序后是升序，如果想让他降序排列，可以使用自己编的cmp函数 #include #include using namespace std; int cmp(int a,int b) { if(a return 1; //升序排列，如果改为 a >b，则为降序,要注意sort()中cmp()的返值只有1和0，不像qsort中存在－1！！！！ else return 0; } int main(){ int i; int a[20]; for(int i=0;i<5;++i) sort(a,a+5,cmp); //范围，很明显这里是a+5 注意，这是必要的，如果是a+4最后一个值a[4]就不会参与排序。 for(i=0;i<5;i++) cout< system("pause"); return 0; } 对二维数组的排序： #include #include #include using namespace std; bool cmp(int *p,int *q) { if(p[0]==q[0]) { if(p[1]==q[1]) { return p[2] } else return p[1] } else return p[0] } int main() { srand(time(0)); int **a=new int*[1000]; for(i=0;i<1000;++i) { a[i]=new int[3]; a[i][0]=rand()%1000; a[i][1]=rand()%1000; a[i][2]=rand()%1000; //printf("%d\t%d\t%d\n",a[i][0],a[i][1],a[i][2]); } sort(a,a+1000,cmp); /*cout<<"After sort"< for(i=0;i<1000;++i) { printf("%d\t%d\t%d\n",a[i][0],a[i][1],a[i][2]); }*/ return 0; } 排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] qsort（基本快速排序的方法，每次把数组分成两部分和中间的一个划分值，而对于有多个重复值 的数组来说，基本快速排序的效率较低，且不稳定）。集成在C语言库函数里面的的qsort函数， 使用三路划分的方法解决排序这个问题。所谓三路划分，是指把数组划分成小于划分值，等于 划分值和大于划分值的三个部分。 具体介绍：-^^ void qsort( void *base, size_t num, size_t width, int (__cdecl *compare ) int compare (const void *elem1, const void *elem2 ) ); qsort（即，quicksort）主要根据你给的比较条件给一个快速排序，主要是通过指针移动实现排序 功能。排序之后的结果仍然放在原来数组中。 参数意义如下: 第一个参数 base 是需要排序的目标数组名（或者也可以理解成开始排序的地址，因为可以写 &s[i]这样的表达式） 第二个参数 num 是参与排序的目标数组元素个数 第三个参数 width 是单个元素的大小（或者目标数组中每一个元素长度），推荐使用sizeof(s[0]） 这样的表达式 第四个参数 compare 就是让很多人觉得非常困惑的比较函数啦。 我们来简单讨论compare这个比较函数（写成compare是我的个人喜好，你可以随便写成什么，比如 cmp 什么的，在后面我会一直用cmp做解释）。 典型的compare的定义是int compare(const void *a,const void *b); 返回值必须是int，两个参数的类型必须都是const void *，那个a,b是随便写的，个人喜好。假 设是对int排序的话，如果是升序，那么就是如果a比b大返回一个正值，小则负值，相等返回0，其他的依次类推，后面有例子来说明对不同的类型如何进行排序。 /******************** * 结构体定义区 * ********************/ typedef struct PID { int16_t pConst; // 比例常数 Proportional Const int16_t iConst; // 积分常数 Integral Const int16_t dConst; // 微分常数 Derivative Const int16_t position; int16_t hisPosition; int16_t lastPosition[10]; }PID; /*********************************************************** * 函数名称：PID参数初始化 * 功能描述：初始化PID参数，并实现P、I、D三个参数的整定 * 参数列表： * 返回结果：无 ***********************************************************/ void PIDInit(PID *iPID) { memset(iPID, 0, sizeof(iPID)); //将所有值清零 iPID->pConst = 2; // 比例常数 Proportional Const iPID->iConst = 0; // 积分常数 Integral Const iPID->dConst = 8; // 微分常数 Derivative Const } /*********************************************************** * 函数名称：PID控制程序 * 功能描述： * 参数列表： * 返回结果：无 ***********************************************************/ void PIDCalc( PID *cPID) { int16_t pGain; //P增益 各种排序算法的总结和比较 1 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort） 归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。 Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。 String sort的几种方法 简介 在之前的一些排序算法中，主要是对一些数值的类型比较的比较多一点。而对于字符串类型来说，它有一些特殊的性质。如果按照传统的排序方法，对于字符串的比较性能其实还取决于字符串的长度以及相似程度。实际上，对于一些字符集的取值在一个比较小的范围内的情况，我们可以有一些比较高效率的算法。这里针对这些特殊的情况进行讨论。 假设给定的排序集合里元素，也就是每个字符都是在一个比较有限的范围里，比如说256个字符范围内。那么，我们可以利用这个特性做一些高效的处理。联想到之前讨论过的counting sort和radix sort方法。这里就是利用了这个特性。 Key-Indexed counting 在之前讨论couting sort的文章里，曾经针对需要排序的元素为数字的情况进行过讨论。counting sort成立的一个前提是它里面所有的元素取值是在一个固定的范围内。假设这个数组里元素能取的最大值是k，那么每次我们要排序的时候只需要声明一个长度为k的数组a。每次碰到一个元素i就将a[i]对应的值加1。这样就统计出来了所有从小到大的元素的值的分布。剩下的就只是从小到达把这些值重新排列输出就可以了。 当然，在一些数字有一定长度而且它们的长度都一样的情况下。我们可以利用从高到低或者从低到高位逐位排序的方式来对数组进行排序。这就是radix sort的基本思路。它本质上就是在每一位的排序上都使用了couting sort。 借鉴前面对于数字的排序，我们对于字符串数组的排序也可以采用类似的方式： Java代码 1.int[] count = new int[R + 1]; 2.//计算每个字符出现的频率 3.for(int i = 0; i < n; i++) 4. count[a[i].charAt(d) + 1]++; 5.//将每个字符出现的频率转换为所在的索引 6.for(int r = 0; r < R; r++) 7. count[r + 1] += count[r]; 8.//将字符分布到具体的数组位置 9.for(int i = 0; i < n; i++) 10. aux[count[a[i].charAt(d)]++] = a[i]; 11.//将结果拷贝回数组 12.for(int i = 0; i < n; i++) 13. a[i] = aux[i]; 上述代码里的R表示当前字符的取值范围。在R值不大的时候它的效率还是相当可观的。在这个计数排序的基础上，我们可以得到一些不同的排序算法。 LSD sort 一种最典型的方法就是从最低位向最高位的方式依次排序，这种和前面的radix sort的思路基本上完全一样。不过在前面的基础上针对字符的情况稍微做一点修改。详细的代码实现如下： Java代码 1.public class LSD { C语言，结构体(struct) 用法 结构(struct) 结构是由基本数据类型构成的、并用一个标识符来命名的各种变量的组合。 结构中可以使用不同的数据类型。 1. 结构说明和结构变量定义 在T urbo C中, 结构也是一种数据类型, 可以使用结构变量, 因此, 象其它 类型的变量一样, 在使用结构变量时要先对其定义。 定义结构变量的一般格式为: struct 结构名 { 类型变量名; 类型变量名; ... } 结构变量; 结构名是结构的标识符不是变量名。 类型为第二节中所讲述的五种数据类型(整型、浮点型、字符型、指针型和 无值型)。 构成结构的每一个类型变量称为结构成员, 它象数组的元素一样, 但数组中 元素是以下标来访问的, 而结构是按变量名字来访问成员的。 下面举一个例子来说明怎样定义结构变量。 struct string { char name[8]; int age; char sex[2]; char depart[20]; float wage1, wage2, wage3, wage4, wage5; } person; 这个例子定义了一个结构名为string的结构变量person, 如果省略变量名 person, 则变成对结构的说明。用已说明的结构名也可定义结构变量。这样定义 时上例变成: struct string { char name[8]; int age; char sex[2]; char depart[20]; float wage1, wage2, wage3, wage4, wage5; }; struct string person; 如果需要定义多个具有相同形式的结构变量时用这种方法比较方便, 它先作 结构说明, 再用结构名来定义变量。 例如: struct string T ianyr, Liuqi, ...; 如果省略结构名, 则称之为无名结构, 这种情况常常出现在函数内部, 用这 种结构时前面的例子变成: 结构是一种用关键字struct声明的自定义数据类型。与类相似，也可以包含构造函数，常数，字段，方法，属性，索引器，运算符和嵌套类型等，不过，结构是值类型。 1.结构的构造函数和类的构造函数不同。 2. a.结构不能包含显式的无参数构造函数。结构成员讲自动初始化为它们的默认值。 b.结构不能包含以下形式的初始值设定类：base（argument-list）； 2.对于结构中的实例字段成员，不能在声明时赋值初始化。 3.声明了结构类型后，可以使用new运算符创建构造对象，也可以不使用new关键字。如果不使用new，那么在初始化所有字段之前，字段将保持未赋值状态且对象不可用。 4.结构不支持继承，即一个结构不能从另一个结构或类继承，而且不能作为一个类的基类。但是，结构从基类OBJECT继承。结构也可以实现接口。 5.什么时候用结构呢？结构使用简单，并且很有用，但是要牢记：结构在堆栈中创建，是值类型，而类是引用类型。每当需要一种经常使用的类型，而且大多数情况下该类型只是一些数据时，使用结构能比使用类获得更佳性能。 结构是值类型，所以会影响性能，但根据使用结构的方式，这种影响可能是正面的，也可能是负面的。正面的影响是为结构分配内存时，速度非常快，因为它们将内联或者保存在堆栈中。在结构超出了作用域被删除时，速度也很快。另一方面，只要把结构作为参数来传递或者把一个结构赋给另一个结构(例如A=B，其中A和B是结构)，结构的所有内容就被复制，而对于类，则只复制引用。这样，就会有性能损失，根据结构的大小，性能损失也不同。注意，结构主要用于小的数据结构。但当把结构作为参数传递给方法时，就应把它作为ref参数传递，以避免性能损失——此时只传递了结构在内存中的地址，这样传递速度就与在类中的传递速度一样快了。另一方面，如果这样做，就必须注意被调用的方法可以改变结构的值。 class和struct有且仅有一个区别，那就是对于class说明的类成员，函数也好，变量也好，如果没有指定类型，缺省是private限定的。而对于struct,则是public的。 结构体数组效率比类数组效率高（不需要装箱合拆箱）。结构体集合（如Hashtable）效率比类集合效率低。集合的元素是引用类型，所以结构体必须进行装箱和拆箱处理。所以类在大的集合中更有效率。 (一)基本思想 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： ①初始状态：无序区为R[1..n]，有序区为空。 ②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 [编辑本段]排序过程 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 65 76] 第六趟排序后13 27 38 49 49 65 [97 76] 第七趟排序后13 27 38 49 49 76 [97 76] 最后排序结果13 27 38 49 49 76 76 97 (二)C语言过程 void selectionSort(Type* arr,long len) { long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n"); for(i=len-1;i>=1;i--) { maxPos=i; for(j=0;j 常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析. 详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key a kind of, this kind of, many kinds of 和 a sort of区别和用法 kind作名词用时，表示种类，比较下面的结构： a kind of +单数名词（不加冠词）一种 this kind of +单数名词（不加冠词）这种 many kinds of +单数名词丨复数名词（不加冠词) 许多种 different kinds of +单数名词丨复数名词（不加冠词) 不同种类 these kinds of +单数名词丨复数名词（不加冠词) 这些种类 all kinds of 单数名词丨复数名词（不加冠词) 各种 This is a new kind of pen.(正）这是一种新型钢笔。 This is a new kind of pens.(误） I like that kind of apple.(正）我喜欢那种苹果 I like that kind of an apple.(误） He saw many kinds of machine.(正）他见到了许多种机器。 He saw many kinds of machines.(正） He wants to buy different kinds of stamp.(正）他想买不同种类的邮票。He wants to buy different kinds of stamps.(正） She lent me three kinds of book.(正）她借给我三种书。 She lent me three kinds of books.(正） He has read all kinds of story-book.(正）他读过各种各样的故事书。 He has read all kinds of story-books. 正） 【比较】 This kind of book is worth reading.这种书值得读。（一种〉 These kinds of books are worth reading.这些种类的书值得读。（多种） What kind of bookis it?它是什么种类的书？ What kind of books are these?这些是什么种类的书？（注意，在what kind lof结构中，kind —般不加s) ■ many kinds of, different kinds of, these kinds of 和 all kinds of 修饰名词作主语时，谓语动词要用复数形式。、 Many kinds of shoes are on show in the shop.商店里展出了许多种类的鞋。 There are all kinds of trees along the lake.沿湖有各种各样的树。 a kind of+名词结构中，形容词通常修饰kind，修饰名词的情况偶尔也有， 但不自然。 ?结构体类型定义 struct [结构体名] { 类型标识符成员名； 类型标识符成员名； ……………. }；成员类型可以是基本型或构造型 struct是关键字,不能省略合法标识符 可省:无名结构体 结构体的说明及结构体变量的定义 例struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }; name num sex age score addr 2字节 2字节 20字节 1字节 4字节 30字节 … ….. 结构体类型定义描述结构 的组织形式,不分配内存 例子图解 ?结构体类型定义 struct [结构体名] { 类型标识符成员名； 类型标识符成员名； ……………. }；成员类型可以是基本型或构造型 struct是关键字,不能省略合法标识符 可省:无名结构体 结构体的说明及结构体变量的定义 (1) 在结构体说明的同时定义结构体变量,例如：struct example { char *name； int age; }guo,zhang；(2)直接定义结构体变量,例如： struct {char *name； int age; }guo,zhang 未给 出结 构体 名 (3) 把定义和说明分开,例如：struct example { char *name； int age; }； struct example guo,zhang；结构体变量占用内存的大小可用sizeof()运算来求出 ?结构体变量的定义 结构体的说明及结构体变量的定义?变量说明形式 struct 结构体名结构体变量名； ?注意： 结构变量的存储类型概念、它的寿命、可见 性及使用范围与普通变量、数组等完全一致。 结构体变量说明必须在结构类型定义之后， 二者也可同时进行。 数据结构各种排序方法的综合比较 结论: 排序方法平均时间最坏时间辅助存储 简单排序O(n2) O(n2) O(1) 快速排序O(nlogn)O(n2)O(logn) 堆排序O(nlogn)O(nlogn)O(1) 归并排序O(nlogn)O(nlogn)O(n) 基数排序O(d(n+rd))O(d(n+rd))O(rd) PS:直接插入排序、冒泡排序为简单排序，希尔排序、堆排序、快速排序为不稳定排序 一、时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为 最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n ); 4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序和堆排序是不稳定的排序方法 语法格式 sort [ -A ] [ -b ] [ -c ] [ -d ] [ -f ] [ -i ] [ -m] [ -n ] [ -r ] [ -u ] [ -o OutFile ] [ -t Character ] [ -T Dir ectory ] [ -y [ Kilobytes ] ] [ -z RecordSize ] [ [ [ FSkip ] [ .CSkip ] [ b ] [ d ] [ f ] [ i ] [ n ] [ r ] ] [ - [ FSkip ] [ .CSkip ] [ b ] [ d ] [ f ] [ i ] [ n ] [ r ] ] ] [ -k KeyDefinition ] [文件 ] 使用说明 sort 命令对 File 参数指定的文件中的行排序，并将结果写到标准输出。如果 File 参数指定多个文件，那么 sort 命令将这些文件连接起来，并当作一个文件进行排序。-（减号）代替文件名指定标准输入。如果您不指定任何文件名，那么该命令对标准输入排序。可以使用 -o 标志指定输出文件。 如果不指定任何标志，sort 命令基于当前语言环境的整理顺序对输入文件的所有行排序。主要参数 -A 使用 ASCII 整理顺序代替当前语言环境的整理顺序在逐字节的基础上排序。 -b 忽略前导空格和制表符，找出字段的第一或最后列。 -c 检查输入是否已按照标志中指定的排序规则进行排序。如果输入文件排序不正确，就返回一个非零值。 -d 使用字典顺序排序。比较中仅考虑字母、数字和空格。 -f 比较前将所有小写字母改成大写字母。 -i 比较中忽略所有非显示字符。 -k KeyDefinition 指定排序关键字。KeyDefinition 选项的格式为： [ FStart [ .CStart ] ] [ ModifIEr ] [ , [ FEnd [ .CEnd ] ][ Modifier ] ]排序关键字包括所有以 FStart 变量指定的字段和 CStart 变量指定的列开头的字符及以 FEnd 变量指定的字段和 CEnd 变量指定的列结束的字符。Modifier 变量的值可以是 b、d、f、i、n 或 r。修饰符与同一字母的标志等价。-m 只合并多个输入文件；假设输入文件已经排序。 -n 按算术值对数字字段排序。数字字段可包含前导空格、可选减号、十进制数字、千分位分隔符和可选基数符。对包含任何非数字字符的字段进行数字排序会出现无法预知的结果。 -o OutFile 将输出指向 OutFile 参数指定的文件，而不是标准输出。OutFile 参数值可以与 File 参数值相同。 -r 颠倒指定排序的顺序。 -t Character 指定 Character 为单一的字段分隔符。 -u 禁止按照排序关键字和选项的所有等同排序（每一组行中一行除外）。 -T Directory 将创建的所有临时文件放入 Directory 参数指定的目录中。 -y[Kilobytes] 用 Kilobytes 参数指定的主存储的千字节数启动 sort 命令，并根据需要增加存储量。（如果 Kilobytes 参数指定的值小于最小存储站点或大于最大存储站点，就以这个最小存储站点或最大存储站点取代）。如果省略 -y 标志，sort 命令以缺省的存储大小启动。-y0 标志用最小存储启动，而 -y 标志（不带 Kilobytes 值）用最大存储启动。sort 命令使用的存储量显著地影响性能。以大存储量对小文件排序将很浪费。 -z RecordSize 如果正在排序的任一行大于缺省的缓冲区大小，要防止出现异常终止。指定 -c 或 -m 标志时，省略排序阶段，使用系统的缺省缓冲大小。如果已排序行超出这一大小，排序异常终止。-z 选项指定排序阶段最长行的记录，因而可在合并阶段分配足够的缓冲区。RecordSize 必须指明等于或大于要合并的最长行的字节值。 （一）不超过8 bytes 的小结构体可以通过EDX:EAX 返回。 本文的范例代码取材于《汇编中函数返回结构体的方法》一文，并在此基础上进行修改和试验。要研究的第一份代码如下，定义一个不超过8 bytes 的小结构体，不超过8 bytes 是因为这个结构体能够用EDX:EAX 容纳，我们之后将看到在release 编译时，编译器能够向返回普通基础类型那样进行返回。 #include return buf; } 上面的get_buffer 返回的是栈上的临时变量空间，在函数返回后，其所在的空间也就被“回收/释放”了，也就是说函数返回的地址位于栈的增长方向上，是不稳定和不被保证的。 那么返回结构体的函数则不同，你可以发现返回结构体的函数是工作正常有效的。在add 函数中有一个临时性结构体t，毫无疑问，t 将在add 函数返回时被释放，但由于t 被当做“值”进行返回，因此编译器将保证add 的返回值对于add 的调用者（caller）来说是有效的。 另外需要明确的一点是，我个人觉得，现实里这种返回结构体的方式比较少见，后面将会看到这样做会产生临时对象和多余拷贝过程，效率不高。常见方法是传递结构体指针。但作为语言上允许的方式，有必要弄清楚编译器如何实现这种方式，而要弄清楚这个问题，需要查看汇编代码。使用VC6 输入上述代码，下面分别给出其汇编代码。 （1）debug 版本，汇编代码如下。 small_struct_debug 下面是实现方式的栈示意图： /******************************************************* 三种基本排序演示程序 说明：此程序适用于理解三种基本排序原理（简单排序，选择排序，插入排序）以及排序的每一个步骤。并且在重要部分有注释. 本人是一家计算机培训机构的兼职教师（培训计算机C二级的），看到许多同学对于排序非常头疼，当然这是二级C的必考点之一，也是贯穿C语言各种知识点的拿分大项。 本程序是自己按照原理写的原创代码，所以定为1分吧（辛苦费吧，一般我搜集的都是免费的(*^__^*) ……，望大家支持下） 此程序我调试运行成功的，如果你复制到编译器不成功，可能是编译器区别造成的。 如果能自己写出这三种排序的同学，我觉得其对C语言基础知识学习就比较牢固了。 时间：2012年12月3日 ********************************************************/ #include STL中sort函数用法简介 做ACM题的时候，排序是一种经常要用到的操作。如果每次都自己写个冒泡之类的O(n^2)排序，不但程序容易超时，而且浪费宝贵的比赛时间，还很有可能写错。STL里面有个sort函数，可以直接对数组排序，复杂度为n*log2(n)。使用这个函数，需要包含头文件。 这个函数可以传两个参数或三个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是[a,b)。简单来说，有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。 拿我出的“AC的策略”这题来说，需要对数组t的第0到len-1的元素排序，就写sort(t,t+len); 对向量v排序也差不多，sort(v.begin(),v.end()); 排序的数据类型不局限于整数，只要是定义了小于运算的类型都可以，比如字符串类string。 如果是没有定义小于运算的数据类型，或者想改变排序的顺序，就要用到第三参数——比较函数。比较函数是一个自己定义的函数，返回值是bool型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数cmp bool cmp(int a,int b) { return a>b; } 排序的时候就写sort(a,a+100,cmp); 假设自己定义了一个结构体node struct node{ int a; int b; double c; } 有一个node类型的数组node arr[100]，想对它进行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b还相同，就按c降序排列。就可以写这样一个比较函数： 以下是代码片段： bool cmp(node x,node y) { if(x.a!=y.a) return x.a if(x.b!=y.b) return x.b>y.b; return return x.c>y.c; } 排序时写sort(arr,a+100,cmp); 最后看一个完整的实例，初赛时的一道题目“文件名排序”。 以下是代码片段： #include 第9章结构体 1．定义以下结构体类型 struct s { int a; char b; float f; }; 则语句printf("%d",sizeof(struct s))的输出结果为【】。 A) 3 B) 7 C) 6 D) 4 2．当定义一个结构体变量时，系统为它分配的内存空间是【】 A）结构中一个成员所需的内存容量 B）结构中第一个成员所需的内存容量 C）结构体中占内存容量最大者所需的容量 D）结构中各成员所需内存容量之和 3．定义以下结构体类型 struct s { int x; float f; }a[3]; 语句printf("%d",sizeof(a))的输出结果为【】 A) 4 B) 12 C) 18 D) 6 4．定义以下结构体数组 struct c { int x; int y; }s[2]={1,3,2,7}; 语句printf("%d",s[0].x*s[1].x)的输出结果为【】 A) 14 B) 6 C) 2 D) 21 5．运行下列程序段，输出结果是【】 struct country { int num; char name[10]; }x[5]={1,"China",2,"USA",3,"France",4, "England",5, "Spanish"}; struct country *p; p=x+2; printf("%d,%c",p->num,(*p).name[2]); A) 3,a B) 4,g C) 2,U D) 5,S 6．下面程序的运行结果是【】。 struct KeyWord { char Key[20]; int ID; }kw[]={"void",1,"char",2,"int",3,"float",4,"double",5}; main() { printf("%c,%d\n",kw[3].Key[0], kw[3].ID); } A) i,3 B) n,3 C) f,4 D) l,4 7．定义以下结构体类型 struct student { char name[10]; int score[50]; float average; }stud1; 则stud1占用内存的字节数是【】。 A) 64 B) 114 C) 228 D) 7 8．如果有下面的定义和赋值，则使用【】不可以输出n中data的值。struct SNode { unsigned id; int data; }n,*p; p=&n; A) p.data B) n.data C) p->data D) (*p).data 9.根据下面的定义，能输出Mary的语句是【】。 struct person { char name[9]; int age; }; struct person class[5]={"John",17,"Paul",19,"Mary",18,"Adam",16}; A) printf("%s\n",class[1].name); B) printf("%s\n",class[2].name); C) printf("%s\n",class[3].name);各种排序算法比较
sort和qsort函数对结构体的二级排序
结构体定义区
各种排序算法的总结和比较
53.String sort 字符串排序的几种方法
c语言结构体用法(转载)
结构体和类的比较
C语言 选择排序
几种常见内部排序算法比较
kind与sort 的区别和用法(a ～ of, this ～ of, many kinds of )
结构体的定义及初始化
数据结构各种排序方法的综合比较
Linux操作系统中排序命令Sort的使用方法
关于返回结构体的函数
C语言三种基本排序(简单排序,选择排序,插入排序)演示程序(含注释、每一个步骤,原创) -修订
STL中sort函数用法简介
C语言结构体习题及答案
相关主题
文本预览