合并排序

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

伪代码：

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

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

#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元素数组的最大元素和最小元素的值

伪代码：

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

代码：

#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);
}

是否稳定

关于是否稳定的问题看这个贴 感觉特别形象

归并是把问题划分为多个小规模问题，将小规模问题解决完之后，再做合并操作。比如将两个已经排好序的子序列做合并操作，此时如果有相同的值分别存在于两个子序列中，我们可以先将左边数组中的数插入到临时数组中，再将右边数组的数插入到临时数组中。这样一来就可以确保相同值相对顺序不变。因此是稳定的。

快速排序

最后

以上就是虚心翅膀为你收集整理的【算法设计与分析】关于分治法的一些（伪）代码整理合并排序快速排序的全部内容，希望文章能够帮你解决【算法设计与分析】关于分治法的一些（伪）代码整理合并排序快速排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。