作业23-快速排序与堆排序

忘是亡心i 2022-12-27 14:14 113阅读 0赞

1-1  
对N个记录进行堆排序，需要的额外空间为O(N)。(F)  
\[解析\]  
辅助空间是O(1)  
需要用到的辅助空间有: rc(根节点的关键值)  
head的左孩子lchild  
head的右孩子rchild  
需要注意的是,随着堆调整的进行,head是不断变化的

堆排序算法实现
    void HeapAdjust(HeapType &H, int head, int tail)
    {
        
    	rc = H.r[head];
    	lChild = 2 * head;
    	rChild = 2 * head + 1;
    	while (lChild <= tail)
    	{
        
    		if (rChild <= tail && H.r[lChild] < H.[rChild].key)
    			bigChild = rChild;
    		else 
    			bigChild = lChild;
    		
    		if (rc < H.r[bigChild])
    		{
        
    			H.r[head] = H.r[bigChild];
    			head = bigChild;
    			lChild = 2 *head;
    			rChild = 2 * head + 1;
    		}
    		else break;
    	}
    	H.r[head] = rc;
    }
    void HeapSort(HeapType &H)
    {
        
    	//初始大顶堆
    	for (int i = H.length / 2; i >= 1; i--)
    		HeapAdjust(H, i, H.length);
    	for (int i = 1; i <= L.length - 1; i++)
    	{
        
    		H.r[0] = H.r[1];
    		H.r[1] = H.r[H.length - i + 1];
    		H.r[H.length - i + 1] = H.r[0];
    		HeapAdjust(H, 1, H.length - i);
    	}
    }
    
    
    堆排序进行的基本操作是 结点的比较和结点的上移
    最坏情况下,每层都需要比较和上移
    含有n个结点的二叉树,其高度是log2n
    因此调整过程的时间复杂度是O(log2N)
    
    初始大顶堆的时间复杂度
    一共需要 N/2 趟堆调整, 每次的复杂度不超过 log2(N)
    所以 T(N) = O( N * log2(N) )
    
    堆排序的时间复杂度 初始化大顶堆的复杂度 + n-1 趟堆调整的时间复杂度
    T(N) = O( N * log2(N) )

1-2  
对N个记录进行简单选择排序，比较次数和移动次数分别为O(N2)和O(N)。  
\[解析\]简单选择排序,每一趟选择出当前最小的记录,  
将其交换到无序块的最前面,如此无序块逐渐变小,N-1 趟完成

2-1  
对N个记录进行堆排序，最坏的情况下时间复杂度是：()  
A.O(logN)  
B.O(N2)  
C.O(N)  
D.O(NlogN)

2-2  
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。  
下列序列中，不可能是快速排序第二趟结果的是：()  
A.5, 2, 12, 28, 16, 32, 72, 60  
B.5, 2, 16, 12, 28, 60, 32, 72  
C.2, 12, 16, 5, 28, 32, 72, 60  
D.2, 16, 5, 28, 12, 60, 32, 72  
\[解析\]不会呀

2-3  
对N个元素采用简单选择排序，比较次数和移动次数分别为：(D)  
A.O(N*logN), O(N*logN)  
B.O(logN), O(N^2)  
C.O(N), O(logN)  
D.O(N^2), O(N)  
\[解析\]比较次数O(N^2),移动只发生在找到无排序块的最小值时  
所以是O(N)

2-4  
有组记录的排序码为\{ 46，79，56，38，40，84 \}，  
则利用堆排序的方法建立的初始堆为：  
A.84，56，79，40，46，38  
B.84，79，56，38，40，46  
C.84，79，56，46，40，38  
D.79，46，56，38，40，80  
\[解析\]根据序列,建立的是完全二叉树  
每趟 都要比较兄弟结点,然后确定 大的兄弟结点  
然后和根节点比较,看看是否需要互换  
若需要,则 互换完之后在调整子树

2-5  
在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，  
如果左指针停止移动，而右指针在同样情况下却不停止移动，  
那么当所有元素都相等时，算法的时间复杂度是多少？()  
A.O(N)  
B.O(NlogN)  
C.O(N2)  
D.O(logN)  
\[解析\]解释过一次

2-6  
对于10个数的简单选择排序，最坏情况下需要交换元素的次数为：  
A.100  
B.9  
C.36  
D.45  
\[解析\]一共循环 n-1 趟,若每次都需要互换, 则需要交换n-1 次

2-7  
对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：(B)  
A.O(N*logN)  
B.O(N^2)  
C.O(N^2*logN)  
D.O(N)  
\[解析\]最坏情况发生在 原序列有序的情况下,需要进行n-1 趟  
每趟比较 O(N) (肯定小于N, 但是平均是 n/2 左右)  
所以最坏复杂度是O(N^2)

2-8  
对N个记录进行堆排序，需要的额外空间为：©  
A.O(NlogN)  
B.O(logN)  
C.O(1)  
D.O(N)  
\[解析\]堆排序只需要rc, rChild, lChild三个变量  
所以空间复杂度是常数

7-2 寻找大富翁 (25分)

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。  
输入格式:

输入首先给出两个正整数N（≤106）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。  
输出格式:

在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。  
输入样例:

8 3  
8 12 7 3 20 9 5 18

输出样例:

20 18 12

//这份代码就是对 顺序表用快速排序
    //但是输入序列发生了变化
    //先输出N 和 序列的元素, 最后输入M
    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    const int MAXNUM = 1e5 + 5;
    typedef int ElemType;
    typedef struct 
    {
        
    	ElemType *elem;
    	int length;
    }SqList;
    
    void CreateList(SqList &L)
    {
        
    	cin >> L.length;
    	L.elem = (ElemType*)malloc(sizeof(ElemType) * (L.length + 1));
    	for (int i = 1; i <= L.length; i++)
    		cin >> L.elem[i];
    }
    int Partition(SqList &L, int low, int high)
    {
        
    	L.elem[0] = L.elem[low];
    	while (low < high)
    	{
        
    		while (low < high && L.elem[high] >= L.elem[0])
    			high--;
    		L.elem[low] = L.elem[high];
    		while (low < high && L.elem[low] <= L.elem[0])
    			low++;
    		L.elem[high] = L.elem[low];
    	}
    	L.elem[low] = L.elem[0];
    	return low;
    }
    void QSort(SqList &L, int low, int high)
    {
        
    	if (low >= high) return ;
    	else 
    	{
        
    		int pivotLoc = Partition(L, low, high);
    		QSort(L, low, pivotLoc - 1);
    		QSort(L, pivotLoc + 1, high);
    	}
    }
    int main()
    {
        
    	//ios::sync_with_stdio(false);
    	SqList L;
    	CreateList(L);
    	int cnt = 0;
    	cin >> cnt;
    	QSort(L, 1, L.length);
    	for (int i = 0, j = L.length; i < cnt; i++, j--)
    		cout << L.elem[j] << ' ';
    	cout << endl;
    	system("pause");
    	return 0;
    }