【算法设计与分析】关于分治法的一些（伪）代码整理合并排序快速排序

100 阅读 0 评论 66 点赞

我是靠谱客的博主虚心翅膀，这篇文章主要介绍【算法设计与分析】关于分治法的一些（伪）代码整理合并排序快速排序，现在分享给大家，希望可以做个参考。

分治法

合并排序
- - 利用分治法求一个元素在数组中的最大位置
  - 利用分治法求一个n元素数组的最大元素和最小元素的值
  - 是否稳定
快速排序

合并排序

利用分治法求一个元素在数组中的最大位置

伪代码：

复制代码

1
2
3
4
5
6
7
8
9
MaxIndex（A, l, r）
//Input: A portion of array A[0…n − 1] between indices l and r (l ≤ r) 
//Output: The index of the largest element in A[l…r]
if l = r return l
else temp1 <- MaxIndex(A, l, (l + r)/2)
temp2 <- MaxIndex(A, (l + r)/2 + 1, r)
if A[temp1] >= A[temp2] return temp1
else return temp2

代码：
（唉本来大二上册学数据结构的时候就应该会的东西）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#include<stdlib.h>
int MaxIndex(int A[],int l,int r){
int temp1 = 0;
int temp2 = 0;
if (l==r){
return l;
}else {
temp1 = MaxIndex(A, l, (l+r)/2);//这里是要递归的
temp2 = MaxIndex(A, (l+r)/2+1, r);//这里也是要递归的 多调试几次就懂了
if (A[temp1] >= A[temp2]) {
return temp1;
}else{
return temp2;
}
}
}
int main(void)
{
int A[8]={32,13,12,4,5,49,2,50};
printf("%dn",MaxIndex(A,0,7));
}

利用分治法求一个n元素数组的最大元素和最小元素的值

伪代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MinMax（A, l, r, minval, maxval）
//Input: A portion of array A[0…n − 1] between indices l and r (l ≤ r) 
//Output: The values of the smallest and largest elements in A[l…r] and assigned to minval and maxval, respectively
if r = l
minval <- A[l]; maxval <- A[l]
else if r - l = 1
if A[l] <= A[r]
minval <- A[l]; maxval <- A[r]
else minval <- A[r]; maxval <- A[l]
else //r - l > 1
MinMax(A, l, (l + r)/2, minval, maxval)
MinMax(A, (l + r)/2 + 1, r, minval2, maxval2)
if minval2 < minval
minval <- minval2
if maxval2 > maxval
maxval <- maxval2

代码：

复制代码

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
#include<stdio.h>
#include<stdlib.h>
void MinMax(int A[], int l, int r, int *minval, int *maxval){
int minval2, maxval2;
if (r == l) {
*minval = A[l];
*maxval = A[l];
} else if (r - l == 1) {
if (A[l] <= A[r]) {
*minval = A[l];
*maxval = A[r];
} else {
*minval = A[r];
*maxval = A[l];
}
} else {
MinMax(A, l, (l + r)/2, minval, maxval);
MinMax(A, (l + r)/2 + 1, r, &minval2, &maxval2);
if (minval2 < *minval) {
*minval = minval2;
}
if (maxval2 > *maxval) {
*maxval = maxval2;
}
}
}
int main(void)
{
int minval, maxval = 0;
int A[8]={32,13,12,4,5,49,2,50};
MinMax(A, 0, 7, &minval, &maxval);//注意这里传的是地址 因为要通过函数改变外面的值
printf("%d %d", minval, maxval);
}