记序排序算法

《记序排序算法》由会员分享，可在线阅读，更多相关《记序排序算法（5页珍藏版）》请在金锄头文库上搜索。

1、 记序排序记序排序是建立在归并操作上的一种有效的排序算法，利用数组元素序号快速定位最大的元素，把最大的元素往后调藉以达到排序作用的排序算法。记序排序基本思想记序排序的算法是：1. 初始化操作，ai指向第一个元素，aj指向最后一个元素；2. 数组下标变量先从数组a0.n-1首端和尾端向中间移动，比较选出关键字较大的n/2个元素放在前半数组；3. 调整指针到前半数组；4. 数组下标变量先从数组a0.n/2首端和尾端向中间移动，比较选出关键字较大的n/4个元素放在前四分之一数组；5. 调整指针到前四分之一数组；6. 经过log2n次循环比较将数值最大的元素放入a1；7. 将最大元素a1与队尾元素an

2、-1交换；8. 初始化操作，ai指向第一个元素，aj指向未排序的最后一个元素；9. 以上2-8步骤执行n遍；记序排序性质最坏时间复杂度o(nlogn)最好时间复杂度o(nlogn)空间复杂度o(1)稳定排序记序排序c语言代码#include#includevoidmain()inti,j,p,t,k,temp,n=100;inta100;printf(排序前:n);for(i=0;in;i+)ai=rand();printf(a%d=%dt,i,ai);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;w

3、hile(k)for(i=0,j=p-1;ij;i+,j-)if(aiaj)temp=ai;ai=aj;aj=temp;k=k/2;p=(p+1)/2;temp=at-1;at-1=a0;a0=temp;t-;printf(排序后:n);for(i=0;in;i+)printf(a%d=%dt,i,ai);if(i+1)%5=0)printf(n);带头结点单链表记序排序#include #include typedef int ElemType;#define N 10 / /定义结点类型 typedef struct Node ElemType data; /单链表中的数据域 struct

4、 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;

5、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=sizeList(L);ElemType temp;while(t) i=l=t; k=1; while(i) i=i/2; k=2*k; k=k/2; while(k) for(i=0,j=l-1;inext; while(s-) q=q-next; if(p-datadata) temp

6、=p-data; p-data=q-data; q-data=temp; k=k/2; l=(l+1)/2; p=q=L-next;k=t;while(-k) q=q-next; temp=p-data; p-data=q-data; q-data=temp; t-; return L; void output(LinkedList head) LinkedList p;p=head-next;doprintf(%3d,p-data);p=p-next;while(p);printf(n); void main()LinkedList L;int n;printf(排序多少数字:n);scanf(%d,&n);L=Creat(n); printf(排序前:n); output(L); LinkedListSortT(L);printf(排序后:n);output(L);