记序排序（最快排序）.doc

记序排序 记序排序是建立在归并操作上的一种有效的 排序算法，利用 数组元素序号快速定位最大的元素，把最大的元素往后调藉以达到排序作用的排序算法。 记序排序基本思想 记序排序的算法是： 初始化操作，a[i]指向第一个元素，a[j]指向最后一个元素； 数组下标变量先从数组a[0..n-1]首端和尾端向中间移动，比较选出关键字较大的n/2个元素放在前半数组； 调整指针到前半数组； 数组下标变量先从数组a[0..n/2]首端和尾端向中间移动，比较选出关键字较大的n/4个元素放在前四分之一数组； 调整指针到前四分之一数组； 经过└log2n┘次循环比较将数值最大的元素放入a[1]； 将最大元素a[1]与队尾元素a[n-1]交换； 初始化操作，a[i]指向第一个元素，a[j]指向未排序的最后一个元素； 以上2-8步骤执行n遍； 记序排序性质 最坏时间复杂度o(nlogn) 最好时间复杂度o(nlogn) 空间复杂度o(1) 稳定排序 记序排序 c语言代码 #includestdio.h?#includestdlib.hvoid?main()?{?int?i,j,p,t,k,temp,n=100;int?a[100];printf(排序前:\n);for(i=0;in;i++){?a[i]=rand();?printf(a[%d]=%d\t,i,a[i]);?if((i+1)%5==0)?????printf(\n);}t=n;?while(t)?????????????????????{?????i=p=t;????k=1;???????????while(i)?????{???????i=i/2;???????k=2*k;?????}?????k=k/2;?????????????????????????while(k)???????????????????{????????????for(i=0,j=p-1;ij;i++,j--)?????????if(a[i]a[j])?????????{???????????temp=a[i];?????????a[i]=a[j];?????????a[j]=temp;????????}?;??????????k=k/2;??????p=(p+1)/2;?????}?temp=a[t-1];a[t-1]=a[0];a[0]=temp;?t--;?}?printf(排序后:\n);for(i=0;in;i++){?printf(a[%d]=%d\t,i,a[i]);?if((i+1)%5==0)?????printf(\n);}} 带头结点单链表记序排序 #include stdio.h #include stdlib.h typedef int ElemType; #define N 10 //////////////////////////////////////////// //定义结点类型 typedef struct Node { ElemType data; //单链表中的数据域 struct Node *next; //单链表的指针域 }Node,*LinkedList; LinkedList Creat(int n) { LinkedList head,r,p; int x,i; head=(Node*)malloc(sizeof(Node)); r=head; printf(输入数字:\n); for(i=n;i0;i--) { scanf(%d,x); p=(Node*)malloc(sizeof(Node)); p-data=x; r-next=p; r=p; } r-next=NULL; return head; } int sizeList(LinkedList L) { Node *p=L; int size = 0; while(p-next) { size++; //遍历链表size大小比链表的实际长度小1 p= p-next; } return size; //链表的实际长度 } LinkedList LinkedListSortT(LinkedList L) { Node *p,*q; int i,j,k,t,m,n,l,s; t=n