算法导论练习题8-3—排序不同长度的数据项

2012-08-02

算法导论习题8-3—排序不同长度的数据项题目：a)给定一个整数数组，其中不同的整数中包含的数字个数可能不同

算法导论习题8-3—排序不同长度的数据项

题目：

a)给定一个整数数组，其中不同的整数中包含的数字个数可能不同，但是该数组中，所有整数中总的数字数为n。说明如何在O(n)时间内对该数组进行排序

b)给定一个字符串数组，其中不同的串包含的字符个数可能不同，但所有串中总的字符个数为n。说明如何在O(n)时间内对该数组进行排序

（注意此处的顺序是指标准的字母顺序，例如，a < ab < b）

思路：

a)先用桶排序方法按数字位数排序O(n)，再用基数排序的方法分别对每个桶中的元素排序O(n)，

其中桶排序中采用了链表来存储各个位上的数字。在该算法中用到了线性时间排序中的三大算法：桶排序，基数排序，计数排序。

具体思路是：首先根据桶排序将不同位数的数字分别放到不同的链表中，位数相同的数字放到同一个链表中。然后再对每一个链表中的所有数字进行排序，所采用的排序算法是基数排序，其中基数排序中采用的稳定排序算法是计数排序。

LinkNode.h定义了链表的节点及其操作。

#include<iostream>using namespace std;class Link;class LinkNode{private:int key;LinkNode * next;public:friend Link;LinkNode():next(NULL),key(-1){}LinkNode(int num):key(num){}LinkNode(int num,LinkNode *node=NULL):key(num),next(node){}~LinkNode(){next=NULL;}int Getkey(){return this->key;}};

Link.h头文件定义了链表常见的操作——插入，删除，得到长度，将链表中的数存储到数组中等。

//链表，实现了链表元素的排列，链表元素个数计算，元素删除//元素添加链表元素查找。#include<iostream>#include"LinkNode.h"using namespace std;class Link{private:LinkNode* head;int length;public:Link():head(new LinkNode()){length=0;}~Link(){MakeEmpty();delete head;}void MakeEmpty(){if(head->next==NULL){return ;}LinkNode * p=head;while(head->next!=NULL){p=head->next;head->next=p->next;delete p;}}//使用数组初始化链表void Init(int a[],int len){int i;this->length=len;LinkNode * p=head;for(i=0;i<len;i++){p->key=a[i];LinkNode *q=new LinkNode();p->next=q;p=p->next;}}int GetLength(){return length;}bool DeleteHead(){if(head==NULL){cout<<"the link is empty!"<<endl;return 0;}else{LinkNode* p;p=head;head=head->next;delete p;length-=1;return 1;}}LinkNode* GetHead(){if(head==NULL){cout<<"the link is empty!"<<endl;return NULL;}return this->head;}int GetElement(int a[]){LinkNode* p=head;int i=0;while(p!=NULL){a[i]=p->key;i++;p=p->next;}return length;}bool InsertInorder(int num){LinkNode* p=head,*t=head;LinkNode *q=new LinkNode(num,NULL);while(p->next!=NULL){t=p;p=p->next;if(num<p->key){t->next=q;q->next=p;length++;return 1;}}//如果插入的数字最大则插入到最后p->next=q;length++;return 1;}bool Insert(int num){LinkNode* p=head;LinkNode *q=new LinkNode(num,NULL);q->next=p->next;p->next=q;length++;return 1;}int ExtractElement(int a[]){int i=0;if(head->next==NULL){return 0;}LinkNode * p=head->next;while(p!=NULL){a[i]=p->key;i++;p=p->next;}return length;}void Print(){LinkNode *p=head->next;while(p!=NULL){cout<<p->key<<" ";p=p->next;}}};

test.cpp实现了该算法的详细过程：

//习题8-3-a，排序不同长度的数据项//思路是先用桶排序,将不同位数的数字放到不同的链表中，然后将同一个链表中的各个数字//按照基数排序来进行排序，其中基数排序中又采用了计数排序来作为稳定的排序算法#include<iostream>#include"Link.h"using namespace std;Link node[100];//计算给定的一个数字的位数，用于某个元素插入哪一个链表。int ComputerDigits(int num){int count=0;if(num==0){return 1;}while(num!=0){count++;num/=10;}return count;}//使用链表实现的桶排序，将数组中的数字按照位数的多少分别插入到各个链表。//其实在插入链表时完全可以采用顺序插入（Link中的InsertInorder函数实现了顺序插入），//但是顺序的插入的时间复杂度较高，因此//此处采用了将数字往链表头插入，然后对该链表进行基数排序int  BucketSort(int a[],int length){int i,count,max=0;for(i=0;i<length;i++){count=ComputerDigits(a[i]);if(max<count)max=count;//链表实现了有序插入，但有序插入的时间复杂度nlgnnode[count].Insert(a[i]);}return max;}//使用计数排序法作为稳定的排序算法//******************//******************//*******************】//计数排序，用于基数排序中稳定的排序算法//其中a为原始数组，divide为分割出来的第k位数字组成的数组//该函数就是利用每一个数中的第k位对a进行排序void CountSort(int a[],int divide[],int length){int c[100]={0},temp[100]={0};int j;//c[i]包含等于i的元素的个数for(j=0;j<length;j++){c[divide[j]]+=1;}//c[i]包含小于等于i的元素的个数for(j=1;j<=9;j++){c[j]+=c[j-1];}//将a[j]放到正确的位置for(j=length-1;j>=0;j--){temp[c[divide[j]]]=a[j];c[divide[j]]-=1;}for(j=length-1;j>=0;j--){a[j]=temp[j+1];}}//**********//***********//**********//将数组a中的第d位数字进行分割，并存放到数组b中void Divide(int a[],int b[],int d,int length){int i,j;int c[100]={0};for(i=0;i<length;i++){c[i]=a[i];}for(i=0;i<length;i++){for(j=1;j<d;j++){c[i]/=10;}b[i]=c[i]%10;}}//基数排序void RadixSort(int a[],int b[],int d,int length){int i;for(i=1;i<=d;i++){Divide(a,b,i,length);CountSort(a,b,length);}}//对每一个链表中的所有数字进行排序，排序算法使用了基数排序void Sort(int a[],int length){int i,count,j,k=0,num;int b[100]={0};int E[100]={0};count=BucketSort(a,length);for(i=1;i<=count;i++){if(node[i].GetLength()!=0){num=node[i].ExtractElement(E);RadixSort(E,b,i,num);}for(j=0;j<node[i].GetLength();j++){a[k++]=E[j];}}}int main(){int a[10];int i;for(i=0;i<10;i++){a[i]=rand()%1000;cout<<a[i]<<' ';}cout<<endl;/*int count=BucketSort(a,10);for(i=1;i<=count;i++){node[i].Print();}*/Sort(a,10);for(i=0;i<10;i++){cout<<a[i]<<" ";}cout<<endl;return 0;}

1楼mishifangxiangdefeng昨天 21:28

代码写得很整齐，一看就能懂

Re: liuzhanchen1987昨天 22:01

回复mishifangxiangdefengn请继续关注我的后面的文章！

Re: liuzhanchen1987昨天 22:01: 回复mishifangxiangdefengn谢谢嘿嘿！

热点排行

编程

算法导论练习题8-3—排序不同长度的数据项