实验1算法分析技术
寻找最大元素和最小元素
【问题描述】
使用一种程序设计语言分别写出一种从一个数组中寻找最大元素和最小元素的算法，并分析其时间复杂性。
【算法设计思路】
从数组的第一项起遍历整个数组，与数组的每一项元素进行比较进行交换，最终返回最大（最小）元素的索引。因只遍历了一遍数组，所以时间复杂度为O(n)。
【算法描述】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int algorithm_max(int a[],int n)
{
int temp=0;
for(int i=0; i<n; i++)
if(a[temp]<a[i])
temp = i;
return temp;
}
int algorithm_min(int a[],int n)
{
int temp=0;
for(int i=0; i<n; i++)
if(a[temp]>a[i])
temp = i;
return temp;
}
|
【复杂性分析】
时间复杂度为O(n).
【实验结果】
附全部代码和实验运行结果截图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <iostream>
using namespace std;
int algorithm_max(int a[],int n)
{
int temp=0;
for(int i=0; i<n; i++)
if(a[temp]<a[i])
temp = i;
return temp;
}
int algorithm_min(int a[],int n)
{
int temp=0;
for(int i=0; i<n; i++)
if(a[temp]>a[i])
temp = i;
return temp;
}
int main()
{
int n;
cin>>n;
int *a = new int[n]();
for (int i=0; i<n ; i++ )
cin>>a[i];
int max_n = algorithm_max(a,n);
int min_n = algorithm_min(a,n);
cout<<"数组中最大的元素为："<<a[max_n]<<endl;
cout<<"数组中最小的元素为："<<a[min_n]<<endl;
delete []a;
}
|
运行结果如下：
排序算法
【问题描述】
使用一种程序设计语言写出选择排序算法的程序，并分析其时间复杂性。
【算法设计思路】
这里实现简单选择排序算法。首先开辟长度为n的动态数组，然后在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。最终数组中序列变为有序。
【算法描述】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void selectsort(int a[],int n)
{
for (int i=0; i<n ; i++ )
{
int k = i;
for (int j=i; j<n ; j++ )
{
if(a[j]<a[k])
k=j;
}
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
|
【复杂性分析】
时间复杂度为O(n^2).
【实验结果】
附全部代码和实验运行结果截图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <iostream>
using namespace std;
void selectsort(int a[],int n)
{
for (int i=0; i<n ; i++ )
{
int k = i;
for (int j=i; j<n ; j++ )
{
if(a[j]<a[k])
k=j;
}
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
int main()
{
int n;
cin>>n;
int *a = new int[n]();
for (int i =0; i<n ; i++ )
cin>>a[i];
selectsort(a,n);
for (int i =0; i<n ; i++ )
cout<<a[i]<< ' ';
delete []a;
}
|
运行结果如下：
有序数组插入新元素
【问题描述】
使用一种程序设计语言写出一种向一个有序数组中插入一个新元素的算法（需要判断原数组是升序还是降序），并分析其时间复杂性。
【算法设计思路】
首先开辟一个长度为2*n的动态数组（方便插入数据后数组整体向后移动）判断原数组是升序还是降序，如果为升序（降序）则将新插入的元素和数组中的最后一个元素比较大小，如果该元素比末尾元素大（小），则直接将其插入数组的末尾成为末位元素。否则，遍历整个数组，将其与数组中的元素比较大小，确定该新元素的位置，将其后面的所有元素整体向后移动一位，然后将新元素插入数组。如果数组中的元素全部相同，则按降序处理。
【算法描述】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| void alo_insert(int k,int a[],int &n)
{
int temp = 0;
if(a[0]<a[1])
{
cout<<"该数组为升序排列"<<endl;
if(k>a[n-1])
{
a[n]=k;
n++;
return;
}
for (int i=0; i<n; i++)
{
if(k<a[i])
{
temp = i;
break;
}
}
for(int i=n-1; i>=temp; i--)
a[i+1] = a[i];
a[temp] = k;
n++;
}
else
{
cout<<"该数组为降序排列"<<endl;
if(k<a[n-1])
{
a[n]=k;
n++;
return;
}
for (int i=0; i<n; i++)
{
if(k>a[i])
{
temp = i;
break;
}
}
for(int i=n-1; i>=temp; i--)
a[i+1] = a[i];
a[temp] = k;
n++;
}
}
|
【复杂性分析】
时间复杂度为O(n).
【实验结果】
附全部代码和实验运行结果截图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <iostream>
using namespace std;
void alo_insert(int k,int a[],int &n)
{
int temp = 0;
if(a[0]<a[1])
{
cout<<"该数组为升序排列"<<endl;
if(k>a[n-1])
{
a[n]=k;
n++;
return;
}
for (int i=0; i<n; i++)
{
if(k<a[i])
{
temp = i;
break;
}
}
for(int i=n-1; i>=temp; i--)
a[i+1] = a[i];
a[temp] = k;
n++;
}
else
{
cout<<"该数组为降序排列"<<endl;
if(k<a[n-1])
{
a[n]=k;
n++;
return;
}
for (int i=0; i<n; i++)
{
if(k>a[i])
{
temp = i;
break;
}
}
for(int i=n-1; i>=temp; i--)
a[i+1] = a[i];
a[temp] = k;
n++;
}
int main()
{
int n;
cin>>n;
int *a = new int[2*n]();
for (int i =0; i<n ; i++ )
cin>>a[i];
int new_n;
cout<<"请输入要插入的元素："<<endl;
cin>>new_n;
alo_insert(new_n,a,n);
for (int i =0; i<n ; i++ )
cout<<a[i]<< ' ';
delete []a;
}
|
运行结果如下：
插入排序
【问题描述】
使用一种程序设计语言写出插入排序算法的程序，并分析其时间复杂性。
【算法设计思路】
将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。初始时，有序序列的长度为1。
【算法描述】
1
2
3
4
5
6
7
8
9
10
11
12
13
| void alo_insertSort(int a[],int n)
{
for (int i=2; i<n; i++)
{
int temp = a[i],j =i;
while(j>0&&temp<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j] = temp;
}
}
|
【复杂性分析】
最好的情况，时间复杂度为O(n)。最坏的情况，时间复杂度是O（n^2）。平均复杂度也是O（n^2）。
【实验结果】
附全部代码和实验运行结果截图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
using namespace std;
void alo_insertSort(int a[],int n)
{
for (int i=2; i<n; i++)
{
int temp = a[i],j =i;
while(j>0&&temp<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j] = temp;
}
}
int main()
{
int n;
cin>>n;
int *a = new int[n]();
for (int i =0; i<n ; i++ )
cin>>a[i];
alo_insertSort(a,n);
for (int i =0; i<n ; i++ )
cout<<a[i]<< ' ';
delete []a;
}
|
运行结果如下：
不重复的插入算法
【问题描述】
使用一种程序设计语言写出一种不重复的插入算法，该算法用于向一个不含重复元素的升序数组中不重复地插入一个新元素。
【算法设计思路】
与第三题思路基本相同，本题不需要考虑出现重复元素的情况，并且已经规定为升序序列，将新插入的元素和数组中的最后一个元素比较大小，如果该元素比末尾元素大（小），则直接将其插入数组的末尾成为末位元素。否则，遍历整个数组，将其与数组中的元素比较大小，确定该新元素的位置，将其后面的所有元素整体向后移动一位，然后将新元素插入数组。
【算法描述】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| void alo_insert(int k,int a[],int &n)
{
int temp = 0;
if(a[0]<a[1])
{
if(k>a[n-1])
{
a[n]=k;
n++;
return;
}
for (int i=0; i<n; i++)
{
if(k<a[i])
{
temp = i;
break;
}
}
for(int i=n-1; i>=temp; i--)
a[i+1] = a[i];
a[temp] = k;
n++;
}
}
|
【复杂性分析】
时间复杂度为O(n)
【实验结果】
附全部代码和实验运行结果截图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
using namespace std;
void alo_insert(int k,int a[],int &n)
{
int temp = 0;
if(a[0]<a[1])
{
{
if(k>a[n-1])
{
a[n]=k;
n++;
return;
}
for (int i=0; i<n; i++)
{
if(k<a[i])
{
temp = i;
break;
}
}
for(int i=n-1; i>=temp; i--)
a[i+1] = a[i];
a[temp] = k;
n++;
}
}
int main()
{
int n;
cin>>n;
int *a = new int[2*n]();
for (int i =0; i<n ; i++ )
cin>>a[i];
int new_n;
cout<<"请输入要插入的元素："<<endl;
cin>>new_n;
alo_insert(new_n,a,n);
for (int i =0; i<n ; i++ )
cout<<a[i]<< ' ';
delete []a;
}
|
运行结果如下：
