一、调试成功程序及说明 1、 题目： 数组A，前m个元素有序（无重复元素），后n个元素有序（无重复元素），整体无序，请设计算法将数组A调整为整体有序且没有重复元素，并分析时间复杂度，要求空间复杂度为O©
算法思想： 我用计数器i来遍历数组A的前m个元素，用计数器j来遍历数组A的后n个元素，来判断A[i]和A[j]的大小关系，从而找出A[j]插入的位置，当然由于数组A的前m个数字和后n个数字都是有顺序的，因此我们只需要遍历一次就行了，不需要反复遍历，因此，我们考虑最坏的情况（即需要插入时，交数字最多的情况），数组A的前m个元素都要大于数组A的后n个元素，因此在每一次比较之后，需要交换j次数字，而j从m取到m+n-1，因此一共需要交换的次数为：，因此时间复杂度为，空间复杂度为，是原地工作，符合要求。
运行结果：
结果分析： 从结果上来看，答案是正确的，但是我们看到时间复杂度居然是，而一般的选择排序或者冒泡排序的时间复杂度也是，因此我们对于条件：数组A前m个无重复有序，数组A后n个重复有序，并没有用的很好，因此我们需要将我们的算法进行优化，而优化出来的算法，时间复杂度为，当时，优化过的算法将比目前的算法好的多，优化的算法将在下面进行展示。
2、 题目： 三个升序有序数组A,B,C（各自均无重复元素）。请设计算法求取三个数组的交集元素，并将结果保存在数组A中请分析时间复杂度，要求空间复杂度为O©
算法思想： 由于要求空间复杂度为O©，因此我们采用上课讲过的内地求交，我们先让数组A和数组B进行内地求并，找到数组A和数组B的交集元素，存储在数组A中，再让新的数组A和数组C进行内地求并，找到数组A和数组C的交集元素，存储在数组A中。由于内地求交的时间复杂度，我们是讲过的，为：，m,n分别为数组A和数组B中元素的个数，因此现在数组元素为m,n,p，因此我们考虑最坏的情况，数组A包含于数组B，那么判断的次数为，因此可以认为他的时间复杂度为。
运行结果：
结果分析： 从结果上来看，无论数组A，B，C中元素的多少，答案都是正确的，并且目前以我的所学知识来说，没有找到可以进行优化的地方了。
附源程序：
int getcommon(int *a, int *b, int *c, int m, int n, int p) { int i,j,k; for (i = 0,j = 0,k = 0; i < m&&j < n;) { if (a[i]<b[j]) i++; else if (a[i] > b[j]) j++; else { a[k] = a[i]; i++; j++; k++; } } for (i = 0,j = 0,k = 0; i < m&&j < p;) { if (a[i]<c[j]) i++; else if (a[i] > c[j]) j++; else { a[k] = a[i]; i++; j++; k++; } } return k; }3、 题目： n个正整数（这些正整数数值<10000），对于这n个数，统计输出其中的相邻数对（差值为1的数对）的个数，相同数据只被统计一次。例如，如果输入数据为1 3 8 2 5 2，那么输出应该是2，表示其中有两个相邻数对，分别是（1,2），（3,2）。注意（2,1）与（1,2）就属于相同数据，不要重复统计。程序运行时，提示用户输入源数据的个数n，然后由系统随机生成n个数据，并显示这n个源数据，然后输出源数据中包含的相邻数对以及总的个数；接着提示用户可以继续输入数值n，如果用户输入的数值小于或等于0，则程序结束；否则程序继续运行。
算法思想： 首先我先随机生成一个元素介于[1,10000]的正整数的数组a，然后我们参考前面的第一题的已给程序，我们先将这个数组展示一下，然后将他排序，只需要排序就行了，不用去重，然后用计数器i来遍历这个数组i，如果a[i]-a[i-1]==1，那么计数器count就加一，最后返回count的值。
运行结果： 源程序：
#include "stdlib.h" #include "math.h" #include "stdio.h" #define N 10000 void getarray(int *a, int *n);//获取数组a void sortdata(int *a, int n);//排序 void showarray(int *a, int n);//显示数组有效元素 int Calc(int *a, int n);//找出有多少个数对 main() { int a[N]; int n; printf("please input data of n:\n"); scanf("%d", &n); while (n > 0) { getarray(a, &n); printf("the original array's:\n"); showarray(a, n); sortdata(a, n); printf("the processed array's:\n"); showarray(a, n); printf("the number of shudui in this array is: %d\n",Calc(a, n)); printf("please input data of n:\n"); scanf("%d",&n); } } void getarray(int *a, int *n) { int i; for (i = 0; i < *n; i++) a[i] = (rand() % 9999)+1;//随机生成小于10000的正整数，这是为了方便程序调试，不能以此作为条件设计算法 } void showarray(int *a, int n) { int i, j; for (i = 0, j = 0; i < n; i++) { printf("%6d", a[i]); j++; if (j % 18 == 0) printf("\n"); } printf("\n"); } void sortdata(int *a, int n)//排序 { int i, j, p; for (i = 0; i < n - 1; i++) { p = i; for (j = i + 1; j < n; j++) { if (a[j] < a[p]) p = j; } if (p != i) { j = a[i]; a[i] = a[p]; a[p] = j; } } } int Calc(int *a, int n) { int i,count=0; for (i=0;i<n-1;i++) { if (a[i+1]-a[i]==1) count++; } return count; }优化算法1： 题目： 数组A，前m个元素有序（无重复元素），后n个元素有序（无重复元素），整体无序，请设计算法将数组A调整为整体有序且没有重复元素，并分析时间复杂度，要求空间复杂度为O©。
算法思想： 让数组A中后n个元素中最小的都比数组A中前m个元素中最大的要大，并且，数组A的前m个元素和后n个元素是有序的，那么整体就是有序的，然后再去掉重复的即可。 我们参考墙的概念，设墙为k,墙左边为排好序的元素，墙右边为未排序的元素，我们先将计数器i指向数组A的前m个元素中的第一个元素A[0]，将计数器j指向数组A的后n个元素中的第一个元素A[m],然后现在我们发现墙的位置就是计数器i的位置，所以不需要再单独开一个计数器k了，然后比较a[i]和a[j]的大小，把小的那个放入墙的左边，直到结束为止，最后再做一个去重处理就行了，而这么做，只需要O(mn)的复杂度。
运行结果： 结果分析： 从运行结果上来看，这个方法显然是正确的，并且他的时间复杂度只有O(mn)，相较于我所想出来的算法来说，具有更加高的效率。并且这个算法的空间复杂度也是O©，即原地工作。
附源程序：
int arrangdata(int *a, int m, int n) { int i,j,temp; for (i=0;i<m;i++) { if (a[i]>a[m]) { temp=a[i]; a[i]=a[m]; a[m]=temp; for (j=m;j<m+n-1;j++) { if (a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }else break; } } } return delrepeat(a,m+n); }