作业22--插入类与交换类排序(防止标题重复)

ゝ一世哀愁。 2022-12-27 14:11 119阅读 0赞

1-1  
对N个不同的数据采用冒泡排序进行从大到小的排序，  
当元素基本有序时交换元素次数肯定最多。(F)  
\[解析\]当序列本身就是从大到小排列的时候, 冒泡排序不需要进行交换

void bubble_sort(int *a, int size)
    {
        
    	int i, j, t;
    	//最坏情况复杂度分析:外部循环n-1次, 比较的次数是 (n-1)n/2
    	//交换的次数是 3*((n-1)n/2) 
    	//时间复杂度是 两者的加和, 因为 整个排序 进行了 (n-1)n/2次比较
    	//和3((n-1)n/2)交换
    	//所以最坏时间复杂度是 O(N^2)
    	
    	//最好情况复杂度:我认为 只执行了 (n-1)n/2 次比较
    	//所以时间复杂度是 O(N^2)
    	for (int i = 1; i < size; i++)
    	{
        
    		for (j = 0; j < size - i; j++)
    		{
        
    			if (a[j] > a[j + 1])
    				swap(a[j], a[j + 1]);
    		}
    	}
    }

1-2  
对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。(F)  
\[解析\]所以在最坏情况下,时间复杂度是O(N^2)

int Partition(SqList &L, int low, int high)
    {
        
    	//最左侧位置(1好位置)空出来,可以用来存放其他元素
    	L.r[0] = L.r[low];
    	//当low == high时, 此时其中一个指针指向的是空位置(可以存放元素)
    	//另一个指针在寻找可以存放到空位置的之后,找不到合适的元素
    	//所以 序列 已经满足条件
    	//这个空位置 最终用来存放 枢轴L.r[0]
    	while (low < high)
    	{
        
    		while (low < high && L.r[0] <= L.r[high])
    			high--;
    		//如果在内部循环中通过 low == high退出
    		//下面的L.r[low] = L.r[high] 其实就是 把 L.r[low]赋值给自己
    		L.r[low] = L.r[high];
    		while (low < high && L.r[0] >= L.r[0])
    			low++;
    		L.r[high] = L.r[low];
    	}
    	L.r[low] = L.r[0];
    	//low位置是中间位置
    	return low;
    }
    
    void QSort(SqList &L, int low, int high)
    {
        
    	//相等 或者输入不合法 直接退出
    	if (low >= high) return ;
    	else 
    	{
        
    		pivotLoc = Partition(L, low, high);
    		QSort(L, low, pivotLoc - 1);
    		QSort(L, pivotLoc + 1, high);
    	}
    }
    平均复杂度: O(N*log2N)
    平均情况下选择的枢轴介于所有元素中间,两侧子序列变成原序列的一半
    从原来长度为N 到 长度为1, 需要log2N趟,
    而每一趟是一趟划分, 第一趟的划分需要访问N个变量
    第二次是 N-1 次
    所以总的 时间复杂度不会超过 N*log2N
    
    最坏情况:原序列就是从小到大排列的,每次 拿最左侧元素当做枢轴,
    每次划分 后, 枢轴左侧序列长度为0, 右侧每次都减少1
    一共需要 n-1 趟划分
    第一次划分n 次比较,第二次划分 n-1
    所以最坏时间复杂度是 O(N^2)

2-15  
对一组包含10个元素的非递减有序序列，  
采用直接插入排序排成非递增序列，  
其可能的比较次数和移动次数分别是：()  
A.100, 100  
B.100, 54  
C.54, 63  
D.45, 44  
\[解析\]比较次数:1 + 2 + … + n-1 = (n-1)n/2 = 45  
移动次数:1 + 2 + … + n-1 = 我觉得还是 45 次呀

直接插入排序 算法实现:
    void InsertionSort(SqList &L)
    {
        
    	int i, j;
    	for (i = 2; i <= L.length; i++)
    	{
        
    		if (L.r[i] >= L.r[i-1])
    			continue;
    		else if (L.r[i] < L.r[i-1]) 
    		{
        
    			L.r[0] = L.r[i];
    			for (j = i-1; L.r[j] > L.r[0]; j--)
    				L.r[j + 1] = L.r[j];
    			
    		}
    		//最终j停留的位置是 小于等于 L.r[0]的
    		//所以右侧才是需要填入的位置
    		L.r[j+1] = L.r[0];
    	}
    }

2-17  
设有100个元素的有序序列，如果用二分插入排序再插入一个元素，  
则最大比较次数是：(A)  
A.7  
B.10  
C.25  
D.50  
\[解析\]log2N = 128

2-2  
设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，  
则最大比较次数是：(D)  
A.1000  
B.999  
C.500  
D.10  
\[解析\]log2(1000) > 9 = 10

2-3  
对于序列\{ 49，38，65，97，76，13，27，50 \}，按由小到大进行排序，  
下面哪一个是初始步长为4的希尔排序法第一趟的结果？(B)  
A.13,27,38,49,50,65,76,97  
B.49,13,27,50,76,38,65,97  
C.49,76,65,13,27,50,97,38  
D.97,76,65,50,49,38,27,13  
\[解析\]第一个子序列为\{49, 76\}  
第二个子序列为\{38, 18\} 排序后得到\{18, 38\}  
delta = 4, 第一个元素位置是1, 第二个元素位置就是 1 + delta = 5;

2-6  
对初始数据序列\{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 \}进行希尔排序。  
若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），  
第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），  
则两趟排序采用的增量（间隔）依次是：()  
A.3, 1  
B.3, 2  
C.5, 2  
D.5, 3  
\[解析\]第一次排序, 位序6 的元素跑到位序为1的 地方  
所以增量为5  
第二次排序, 位序为5的元素跑到位序为2的位置  
所以增量为3

2-1  
对N个不同的数据采用冒泡算法进行从大到小的排序，  
下面哪种情况下肯定交换元素次数最多？(A)  
A.从小到大排好的  
B.从大到小排好的  
C.元素无序  
D.元素基本有序  
\[解析\]从小到大排好的序列, 每次都要把 首位元素后移到 最后的位置  
所以移动次数最多

2-8  
对于7个数进行冒泡排序，需要进行的比较次数为：©  
A.7  
B.14  
C.21  
D.49  
\[解析\]最坏情况: 比较次数= 6 + 5 + … + 1 = 6 \* 7 /2 = 21

2-9  
采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，  
正确的是：©  
A.每次划分后，先处理较长的分区可以减少递归次数  
B.每次划分后，先处理较短的分区可以减少递归次数  
C.递归次数与每次划分后得到的分区处理顺序无关  
D.递归次数与初始数据的排列次序无关  
\[解析\]递归是对两侧子序列分别递归,递归深度取决于两侧的子序列  
与递归顺序无关

2-10  
对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：©  
A.O(N)  
B.O(N*logN)  
C.O(N^2)  
D.O(N^2*logN)  
\[解析\]快速排序,最坏时间复杂度,在序列已经有序的情况下(从小到大)  
每次取出最左侧元素作为枢轴, 那么划分后左侧序列长为0,右侧长度减小1  
所以 一共需要 n-1 趟, 第一趟需要n次比较, 第二次需要n-2 次比较  
所以时间复杂度在O(N^2)

2-11  
有组记录的排序码为\{46，79，56，38，40，84 \}，  
采用快速排序（以位于最左位置的对象为基准而）  
得到的第一次划分结果为：(D)  
A.\{38,46,79,56,40,84\}  
B.\{38,79,56,46,40,84\}  
C.\{38,46,56,79,40,84\}  
D.\{40,38,46,56,79,84\}  
\[解析\]46 作为枢轴,划分结果为\{40, 38, 46, 56,79,84\}  
注意先是high从右往左比较, 然后再low从左往右比较,

2-12  
在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，  
如果左右指针都不停止移动，那么当所有元素都相等时，  
算法的时间复杂度是多少？(D)  
A.O(logN)  
B.O(N)  
C.O(N\*logN)  
D.O(N^2)  
\[解析\]每次都是high移动到最左侧  
第一次比较n 次  
第二次n-1 次.  
一共划分n-1 趟  
所以时间复杂度还是O(N^2)

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    #include <malloc.h>
    using namespace std;
    typedef  int  KeyType;
    typedef  struct {
                              
      KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
      int Length;      
    }SqList;
    void  CreatSqList(SqList *L)
    {
        
    	cin >> L->Length;
    	L->elem = (KeyType*)malloc(sizeof(KeyType) * (L->Length + 1));
    	for (int i = 1; i <= L->Length; i++)
    	{
        
    		cin >> L->elem[i];
    	}
    }/*待排序列建立，由裁判实现，细节不表*/ 
    void InsertSort(SqList &L)
    {
        
    	int i, j;
    	for (i = 2; i <= L.Length; i++)
    	{
        
    		if (L.elem[i - 1] > L.elem[i])
    		{
        
    			L.elem[0] = L.elem[i];
    			for (j = i - 1; L.elem[j] > L.elem[0]; j--)
    			{
        
    				L.elem[j + 1] = L.elem[j];
    			}
    			L.elem[j + 1] = L.elem[0];
    		}
    	}
    }
    
    int main()
    {
        
      SqList L;
      int i;
      CreatSqList(&L);
      InsertSort(L);
      for(i=1;i<=L.Length;i++)
       {
                
          printf("%d ",L.elem[i]);
        }
    	system("pause");
      return 0;
    }

6-1 希尔排序的实现 (10分)

本题要求实现一趟希尔排序函数，待排序列的长度1<=n<=1000。  
函数接口定义：

void ShellInsert(SqList L,int dk);

其中L是待排序表，使排序后的数据从小到大排列。 \#\#\#类型定义：

typedef int KeyType;  
typedef struct \{  
KeyType \*elem; /*elem\[0\]一般作哨兵或缓冲区*/  
int Length;  
\}SqList;

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10  
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。  
1 2 3 4 5 6 8 9 10 12

#include<stdio.h>
    #include<stdlib.h>
    typedef  int  KeyType;
    typedef  struct {
                              
      KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
      int Length;      
    }SqList;
    void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
    void  ShellInsert(SqList L,int dk);
    void  ShellSort(SqList L);
    
    int main()
    {
        
      SqList L;
      int i;
      CreatSqList(&L);
      ShellSort(L);
      for(i=1;i<=L.Length;i++)
       {
                
         printf("%d ",L.elem[i]);
       }
      return 0;
    }
    
    void ShellInsert(SqList &L, int dk)
    {
        
    	int i, j;
    	for (i = dk + 1; i <= L.Length; i++)
    	{
        
    		if (L.elem[i - dk] > L.elem[i])
    		{
        
    			//这里的循环终止条件 多了个 j > 0
    			//不能少,否则会越界访问
    			//但是在插入排序的算法中你会发现没有这条,
    			//因为插入排序的终止条件不会发生越界访问
    			for (j = i - dk; j > 0 && L.elem[j] > L.elem[0]; j-=dk)
    				L.elem[j + dk] = L.elem[j];
    			L.elem[j + dk] = L.elem[0];
    		}
    	}
    }
    void ShellSort(SqList L)
    {
        
      /*按增量序列dlta[0…t-1]对顺序表L作Shell排序,假设规定增量序列为5,3,1*/
       int k;
       int dlta[3]={
        5,3,1};
       int t=3;
       for(k=0;k<t;++k)
           ShellInsert(L,dlta[k]);
    } 
    /*你的代码将被嵌在这里 */

7-2 人以群分 (25分)

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。  
输入格式：

输入第一行给出一个正整数N（2≤N≤105）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过231。  
输出格式：

按下列格式输出：

Outgoing \#: N1  
Introverted \#: N2  
Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。  
输入样例1：

10  
23 8 10 99 46 2333 46 1 666 555

输出样例1：

Outgoing \#: 5  
Introverted \#: 5  
Diff = 3611

#include <iostream>
    #include <cstdlib>
    #include <malloc.h>
    
    using namespace std;
    const int MAXNUM = 1e5 + 5;
    typedef int ElemType;
    typedef struct 
    {
        
    	ElemType *elem;
    	int Length;
    }SqList;
    
    void CreatSqList(SqList &L)
    {
        
    	cin >> L.Length;
    	L.elem = (ElemType*)malloc(sizeof(ElemType)*sizeof(L.Length + 1));
    	for (int i = 1; i <= L.Length; i++)
    		cin >> L.elem[i];
    }
    void InsertionSort(SqList &L)
    {
        
    	int i, j;
    	for (i = 2; i <= L.Length; i++)
    	{
        
    		if (L.elem[i - 1] > L.elem[i])
    		{
        
    			L.elem[0] = L.elem[i];
    			for (j = i - 1; L.elem[j] > L.elem[0]; j--)
    			{
        
    				L.elem[j + 1] = L.elem[j];
    			}
    			L.elem[j + 1] = L.elem[0];
    		}
    	}
    }
    
    int main()
    {
        
    	SqList L;
    	CreatSqList(L);
    	InsertionSort(L);
    	int N1 = 0, N2 = 0;
    	int sum1 = 0, sum2 = 0;
    	for (int i = 1; i <= L.Length /2; i++)
    	{
        
    		N1++;
    		sum1 += L.elem[i];
    	}
    	for (int i = L.Length /2 + 1; i <= L.Length; i++)
    	{
        
    		N2++;
    		sum2 += L.elem[i];
    	}
    	
    	cout << "Outgoing #: " << N1 << endl;
    	cout << "Introverted #: " << N2 << endl;
    	cout << "Diff = " << sum2 - sum1 << endl;
    	system("pause");
    	return 0;
    }