一、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 }
②、结果
