一、2016年43题
1、问题描述
2、答案解析
（1）、算法的基本设计思想
由题意知，将最小的n/2个元素放进A1中，剩余元素放在A2中，分组结果即可满足题目要求。
仿照快速排序的思想，基于枢轴把n个整数划分成两个子集，根据划分后枢轴所处的位置i分别处理：
①、若i=n/2，则分组完成，算法结束；
②、若i<n/2，则枢轴及之前的所有元素均属于A1，继续对i之后的元素划分；
③、若i>n/2，则枢轴及之后的所有元素均属于A2，继续对i之前的元素划分。
基于设计思想实现的算法，不需要对全部元素进行全排序，平均时间复杂度是O(n)，空间复杂度是O(1)。
3、代码实战
①、代码
1 #include<stdio.h>
2 #include<stdlib.h>
3 int SetPartition(int *A,int n)
4 {
5 int pivot,low=0,low0=0,high=n-1,high0=n-1,flag=1,k=n/2,i;
6 int s1=0,s2=0;
7 while(flag)
8 {
9 pivot=A[low];//选择枢轴
10 while(low<high)
11 {
12 while(low<high&&pivot<=A[high])
13 {
14 --high;
15 }
16 if(low!=high)
17 {
18 A[low]=A[high];
19 }
20 while(low<high&&pivot>=A[low])
21 {
22 ++low;
23 }
24 if(low!=high)
25 {
26 A[high]=A[low];
27 }
28 }
29 A[low]=pivot;
30 if(low=k-1)
31 {
32 flag=0;
33 }
34 else//继续划分
35 {
36 if(low<k-1)
37 {
38 low0=++low;
39 high=high0;
40 }
41 else
42 {
43 low=low0;
44 high0=--high;
45 }
46 }
47 }
48 for(i=0;i<k;i++)
49 {
50 s1=s1+A[i];
51 }
52 for(i=k;i<n;i++)
53 {
54 s2=s2+A[i];
55 }
56 return s2-s1;
57 }
58
59 //主函数
60 int main()
61 {
62 int A[10]={4,1,12,18,7,13,18,16,2,15};
63 int difference;
64 difference=SetPartition(A,10);
65 printf("%d\n",difference);
66 return 0;
67 }
②、结果
二、2022年42题
1、问题描述
2、答案解析
思路一：最小值（插入排序思想）
1）、算法思想
1 定义含10个元素的数组A，初始时元素值均为该数组类型所能表示的最大数MAX 2 for M中的每个元素s 3 if(s<A[9]) 丢弃A[9]并将s按照升序插入到A中;(插入排序算法) 4 当数据全部扫描完毕，数组A[0]-A[9]保存的即是最小的10个数。
2）、复杂度分析
①、时间复杂度：O(n)，每次要插入时都是需要对小数组A进行遍历的；
②、空间复杂度：O(1)，中间过程额外需要常数个变量。
思路二：堆（堆排序思想）
1）、算法思想
1 定义含10个元素的大根堆H，元素值均为该堆元素类型能表示的最大数MAX 2 for M中的每个元素s 3 if(s<H的堆顶元素) 删除堆顶元素并将s插入到H中; 4 当数据全部扫描完毕，堆H中保存的即是最小的10个元素。
2）、复杂度分析
算法平均情况下的时间复杂度是O(n)，空间复杂度是O(1)。
进一步分析：
先用A[0:9]原地建立大根堆（注意这里不能使用小根堆），遍历A[10:n]，每个元素A[i]逐一和堆顶元素A[0]进行比较，如果A[i]大于等于堆顶元素A[0]，不进行任何操作，如果该元素小于栈顶元素A[0]，那么就删除堆顶元素，将该元素放入栈顶，即令A[0]=A[i]，然后将A[0:9]重新调整为大根堆。
最后堆A[0:9]中留存的元素即为最小的10个数。
思路三：快速排序
通过快速排序，分割思想，第一次知道n/2位置，再次partition得到n/4，最终缩小为10个，就拿到了最小的10个元素，遍历的平均次数是n+n/2+n/4+…+1，次数是2n，因此时间复杂度是O(n)，由于不进行快排，只是记录剩余部分、起始和结束，因此空间复杂度是O(1)。
3、代码实战
①、代码
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4 //顺序表的数据结构定义
5 typedef struct{
6 int *elem;
7 int len;
8 }SSTable;
9
10 //初始化顺序表
11 void ST_Init(SSTable &ST,int n)
12 {
13 ST.len=n;
14 ST.elem=(int*)malloc(sizeof(int)*ST.len);
15 int i;
16 srand(time(NULL));
17 for(i=0;i<ST.len;i++)//进行随机数生成
18 {
19 ST.elem[i]=rand();
20 }
21 }
22
23 //打印元素
24 void ST_Print(SSTable ST)
25 {
26 int i=0;
27 for(i=0;i<10;i++)
28 {
29 printf("%3d",ST.elem[i]);
30 }
31 printf("\n");
32 }
33
34 //交换两个元素
35 void swap(int &a,int &b)
36 {
37 int tmp;
38 tmp=a;
39 a=b;
40 b=tmp;
41 }
42
43 //调整子树
44 void AdjustDown(int *A,int k,int len)
45 {
46 int dad=k;
47 int son=2*dad+1;
48 while(son<=len)
49 {
50 if(A[son]<A[son+1]&&son+1<=len)
51 {
52 son++;
53 }
54 if(A[son]>A[dad])
55 {
56 swap(A[son],A[dad]);
57 dad=son;
58 son=2*dad+1;
59 }
60 else
61 {
62 break;
63 }
64 }
65 }
66
67 //堆排序
68 void Heap_Sort(int *A,int len)
69 {
70 int i;
71 //先对前10个元素建立大根堆
72 for(i=len/2;i>=0;i--)
73 {
74 AdjustDown(A,i,len);
75 }
76 //比较剩余A[10]到A[99999]元素，小于堆顶元素，就放入A[0]，继续调整10个元素为大根堆
77 for(i=0;i<100000;i++)
78 {
79 if(A[i]<A[0])
80 {
81 A[0]=A[i];
82 AdjustDown(A,0,9);//继续调整为大根堆
83 }
84 }
85 }
86 //主函数
87 int main()
88 {
89 SSTable ST;
90 ST_Init(ST,100000);
91 Heap_Sort(ST.elem,9);
92 ST_Print(ST);
93 return 0;
94 }
②、结果
标签：Note8,10,int,复杂度,元素,len,NOTE,low,真题 From： https://www.cnblogs.com/Alkaid-1192924906/p/17292941.html