链表排序2015/4/17周五下午18:25:04
另一方面，顺序表的排序顺序表的排序实际上是结构体中的关键字的排序。
c语言版：自定义结构：
类型结构节点{ int age； int height； 输入宽度； }节点； 目前，根据其中的age排序，有两种想用c语言实现的：
1、自定义交换函数，按照常用的交换排序方法排序即可。 这里用快速排序实现。
实现快速队列：
//自定义结构交换void swap (节点* a，节点* b )//指定排序的节点) nodet=*a； *a=*b； *b=t； () ) ) ) ) ) ) elemtype*elem，int left，int right ) /注意这里是封闭区间(if ) leftright ) { int temp=elem [ right ] int j=left； while(jright ) if(elem[j].age=temp ) /此处也指定=可以在波段中更换) I； swap(Elem[I]，elem[j]； (j； }swap(elem[I1]，elem[right]； int r=i 1； 快速排序(elem，left，r-1 )； 快速排序(elem，r 1，right )； }算法的平均复杂度： o(nlogn )，最坏情况是复杂度： o (N2 )。 空间复杂度o(n )。 2、当然c语言中也内置了排序算法qsort，位于stdlib.h头文件中，核心实现了快速排序。
函数原型：
voidqsort(void*base，int nelem，int width，int ) fcmp ) const void *，const void * )；
含义：对1数组的起始地址进行排序。 2数组中要排序的元素数。 3各元素占用空间的大小。 指向4函数的指针
函数的重要比较函数：
此函数是一种自定义对象排序方式的方法。 可以按从大到小的顺序对整数、字符串和自定义结构进行排序。 比较函数一般这样写：
intCMP(constvoid*a，const void* b ) return ) ) (node * (a ).age ) ) ) node * (b ).age； }结构体节点的比较是这样写的。 返回整数值。
也可以用符号替换减号。 从大到小顺序。 如果比较函数的返回值大于0，则qsort视为ab，如果比较函数的返回值为0
qsort认为a和b这两个要素相等，如果返回小于零的qsort则认为是a
c版：因为c包含c语言，所以上面的列也可以在c中运行。
在这里，我将介绍c中更好的方法。
1，http://www.Sina.com /，给结构体一种新的比较方法，以达到序列化的目的。 简言之，创建结构并定义在比较两个结构时在哪个字段中进行比较。 直接上传代码：
注意：在C中可以在结构体”上披外套，而无需typedef。
结构节点{ int age； itn height； 输入宽度； booloperator(structnodeb ) const //这里是const { return age b.age； }； 经过以上定义，继续写
节点a，b； 为字段指定值后，比较ab .的含义为a.age b.age。 这样，上面的快速排序代码就不用特意指定用age进行排序了。 结构可以直接赋值。 这里不需要重载=号码。
更换电线和上面的一样。 改写上面的快速排序代码：
语音快速排序(elemtype * a，int left，int right ) if ) leftright ) { ElemType temp=a[right]； //这里不用指定为age，有通用型。 int i=left-1； int j=left； while(jright ) {if ) a[j]a[right]}
{ ++i; Swap(&a[j],&a[i]); } j++; } Swap(&a[i+1],&a[right]); int r = i+1; QuickSort(a, left, r-1); QuickSort(a, r+1, right); }}2、使用sort，同样c++中也有特有的排序函数，sort,它的内部是很多高效率的排序算法的整合，根据待排序的数据量选择不同的排序方法，是时间最优。
该函数位于头文件#include <algorithm.h>中。
函数原型:使用了模板类， 就是第三个参数(自定义排序方式)是可选的。
template< class RandomIt >
void sort( RandomIt first, RandomIt last ) (1);
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp ); (2)
sort使用的c++中的模板template， 就可以对任何定义了比较关系的集合进行排序了。模板类，相当于纯面向对象语言，如c#和Java，中的泛型概念。
如何使用sort?
1、配合结构体中的重载一起使用：
我们在上面定义了重载’<‘运算符的结构体，就可以直接用sort排序了。
直接sort(node,node+n);两个参数，相当于数组的始末指针。
不过注意，这里是按从小到大的顺序排的，因为上面重载的时候是<对<号，如果重载小于号的时候，在函数体内写的却是age>b.age,结果就是从大到小排序了。
2、不使用结构体运算符的重载，使用sort的第三个参数(自定义排序方法)来实现排序的效果。
bool cmp(ElemType a, ElemType b) { return a.age > b.age; }这样的话主函数里用的时候写sort(a,a+n,cmp);就能排序了。
二、链式表的排序单链表不适合快速排序，双向链表才适合快速排序，这里我们用选择排序法排序单链表，用快速排序法，排序双向链表：
单链表
定义单链表：
有关选择排序的知识，请看这里：wikipedia:选择排序；
直接上代码：
下面画图来解释：
实际代码：
inline void Swap(LinkNode *p, Linknode *q){ LinkNode temp = *p; temp.next = q->next; q->next = p->next; *p = *q; *q = temp; }* 双向链表实现快速排序
1、双向链表定义： struct Node { int data; struct Node *pri, *next; };2、新建双链表 Node* CreateDulNode(int *a, int n) //将数组元素存到链表中 { Node *head = (Node*)malloc(sizeof(Node)); head->next = NULL; head->pri = NULL; Node *p = head; int i = 0; Node *q = NULL; while (i<n) { q = (Node*)malloc(sizeof(Node)); q->data = a[i]; q->next = p->next; q->pri = p; p->next = q; p = q; i++; } q->next = head; head->pri = q; return head; }3、快速排序 //其实就是数组的排序原理，有些小细节要注意 //调用QuickSort(L->next, L->pri); void QuickSort(Node *Left, Node* right) //闭区间 { if (Left->pri != right) //这里当right在left左边是结束 { Node *temp = right; Node *p = Left->pri; Node *q = Left; while (q != right) { if (q->data < temp->data) { p = p->next; Swap(p, q); } q = q->next; } p = p->next; Swap(p, temp); // OutPut2(Left,right); //测试输出函数 QuickSort(Left, p->pri); QuickSort(p->next, right); } }4、关键的交换函数，不过也和单链表的交换差不多了 void Swap(Node *p, Node *q) { Node temp = *p; temp.next = q->next; temp.pri = q->pri; q->next = p->next; q->pri = p->pri; *p = *q; *q = temp; }5、测试输出函数 void OutPut2(Node *Left, Node *right) { Node *p = Left; while (p!=right) { cout << p->data << " "; p = p->next; } cout << right->data << " "; //单独输出最后一个 cout << endl; }实验结果：总结: 以前排序都是在数组上排序，现在学了链表，也想实现快速排序。总之，本质上没啥区别，算法流程都差不多，只是操作上的不同。