作业24-归并排序与基数排序(防止题目重复)

太过爱你忘了你带给我的痛 2022-12-28 00:44 184阅读 0赞

1-3  
对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。()  
\[解析\]归并的数量级在O(logN)?  
每上下相邻的两层之间,从上层到下层的过程就是一趟归并  
满二叉树深度为k的二叉树的最后一层结点个数为2^k - 1  
所以叶子数为N的完全二叉树,它的深度为log2N  
归并的趟数就是O(logN)

void Merge(SqList L, int low, int mid, int high, SqList &res_L)
    {
        
    	p_left = low;
    	p_right = mid + 1;
    	p_res = low;
    	while (p_left <= mid && p_righ <= high)
    	{
        
    		
    	}
    }
    
    //T是辅助空间,和原顺序表一样大
    void MergeSort(SqList L, int low, int high, SqList &T)
    {
        
    	if (low == high)
    		T.elem[low] = L.elem[low];
    	else
    	{
        
    		mid = (low + high) / 2;
    		MergeSort(L, low, mid, T);
    		MergeSort(L, mid + 1, high, T);
    		Merge(T, low, mid, high, L);
    	}	
    }

1-2  
基数排序是稳定的算法。(T)  
\[解析\]若基数排序 用的是队列或者顺序表,所以 对相同的关键字  
在存储进基数对应的表里的顺序不发生改变,从这个表中取出时也不发生改变

1-4  
To sort N records by merge sort,  
the number of merge runs is O(NlogN).(F)  
\[解析\]O(logN)

1-5

Mergesort is stable.(F)

2-8  
对N个记录进行归并排序，归并趟数的数量级是(B)  
A.O(logN)  
B.O(N)  
C.O(NlogN)  
D.O(N2)

2-9  
对N个记录进行归并排序，空间复杂度为：(B)  
A.O(logN)  
B.O(N)  
C.O(NlogN)  
D.O(N2)  
\[解析\]需要开辟与原数组相同大小的辅助空间

2-10  
给出关键字序列\{ 321，156，57，46，28，7，331，33，34，63 \}，  
下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和  
收集的结果？(B)  
A.→331→321→33→63→34→156→46→57→7→28  
B.→321→331→33→63→34→156→46→57→7→28  
C.→156→28→321→331→33→34→46→57→63→7  
D.→57→46→28→7→33→34→63→156→321→331  
\[解析\]根据最低位按照和原序列的相对位置排序  
321 331 33 63 34 156 46 57 7 28

2-11  
对给定序列\{ 110，119，7，911，114，120，122 \}采用次位优先  
（LSD）的基数排序，则两趟收集后的结果为：©  
A.7, 110, 119, 114, 911, 120, 122  
B.7, 110, 119, 114, 911, 122, 120  
C.7, 110, 911, 114, 119, 120, 122  
D.110, 120, 911, 122, 114, 7, 119  
\[解析\]  
需要注意的是 7 的倒数第 2 位是 0, 也就是7 == 007  
7 110 911 114 119 120 122

2-12  
给出关键字序列\{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 \}，  
下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和  
收集的结果？©  
A.→331→431→33→63→24→56→46→57→7→28  
B.→56→28→431→331→33→24→46→57→63→7  
C.→431→331→33→63→24→56→46→57→7→28  
D.→57→46→28→7→33→24→63→56→431→331  
\[解析\]431 331 33 63 24 56 46 57 7 28

2-4  
输入105个只有一位数字的整数，可以用O(N)复杂度将其排序的算法是：  
A.快速排序  
B.插入排序  
C.希尔排序  
D.基数排序  
\[解析\]基数排序

7-2 链式基数排序 (20分)

实现链式基数排序，待排序关键字n满足1≤n≤1000，最大关键字数位≤5。  
输入样例：

第一行输入待排序个数n（1≤n≤1000）,再输入n个数(n的数位≤5)。

10  
278 109 63 930 589 184 505 269 8 83

输出样例：

输出每趟分配-收集后链表中的关键字，趟数为序列中最大值的数位（如样例中930的数位为3），每行结尾有空格。

930 63 83 184 505 278 8 109 589 269  
505 8 109 930 63 269 278 83 184 589  
8 63 83 109 184 269 278 505 589 930

//凎!考完六级刚难受着,又得写链式基数排序
    //没写完,不写了,不会
    #include <iostream>
    #include <cstdlib>
    #include <malloc.h>
    using namespace std;
    typedef int ElemType;
    typedef struct LNode
    {
        
    	ElemType data;
    	struct LNode *Next;
    }LNode, *LinkList;
    
    typedef struct 
    {
        
    	LinkList L;
    }Bucket;
    
    void CreatList(LinkList L, int len)
    {
        
    	L = (LNode*)malloc(sizeof(LNode));
    	if (L == NULL) exit(OVERFLOW);
    	L->Next = NULL;
    	LNode *p = L;
    	while (len--)
    	{
        
    		LNode *tempNode = (LNode*)malloc(sizeof(LNode));
    		if (tempNode == NULL) exit(OVERFLOW);
    		cin >> tempNode->data;
    		tempNode->Next = NULL;
    		p->Next = tempNode;
    		p = tempNode;
    	}
    }
    
    void InsertToList(LinkList &L, ElemType e)
    {
        
    	LNode *p = L;
    	while (p->Next != NULL)
    	{
        
    		p = p->Next;
    	}
    	LNode *temp_Node = (LNode*)malloc(sizeof(LNode));
    	temp_Node->data = e;
    	temp_Node->Next = NULL;
    	p->Next = temp_Node;
    }
    void Add(LinkList &LwithHead, LinkList &L)
    {
        
    	LNode *p = LwithHead;
    	while (p->Next != NULL)
    		p = p->Next;
    	p->Next = L;
    	L = NULL;
    }
    ElemType GetElemAt(LinkList list, int i)
    {
        
    	ElemType e;
    	LNode *p = list->Next;
    	while (i-- && p != NULL)
    		p = p->Next;
    	e = p->data;
    	return e;
    }
    void GetRoundCount(LinkList list)
    {
        
    	//不想邪了
    	return 10;
    }
    int GetRadixNumber(ElemType e, int k)
    {
        
    	while (k--)
    		e /= 10;
    	return e % 10;
    }
    
    void EnBucket(Bucket &bucket, ElemType e)
    {
        
    	InsertToList(bucket.L, e);
    }
    void Distribute(LinkList &list, int len, Bucket *bucket, int k)
    {
        
    	for (int i = 1; i <= len; i++)
    	{
        
    		int radix = GetRadixNumber(GetElemAt(list, i), k);
    		EnBucket(bucket[radix], GetElemAt(list, i));
    	}
    }
    
    void Collect(Bucket *bucket, LinkList &list)
    {
        
    	int j = 1;
    	for (int i = 0; i < 10; i++)
    	{
        
    		Add(list, bucket[i].L);
    	}
    }
    
    void RadixSort(LinkList &list)
    {
        
    	Bucket Bucket[10];
    	for (int i = 0; i < 10; i++)
    		Bucket[i].L = NULL;
    	int max_num_len = GetRoundCount(list);
    
    }
    int main()
    {
        
    	int len;
    	LinkList list;
    	Bucket bucket[10];
    	cin >> len;
    	CreatList(list, len);
    	
    	return 0;
    }