在计算机科学中,分治算法是一种很重要的算法。
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后可以直接求解子问题,原问题的解即子问题的解的合并。
对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决,否则将其分解为 k 个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫作分治算法。
1) C语言分治算法所能解决的问题一般具有以下几个特征。
2) C语言分治算法的 3 个步骤如下。
从小到大快速交换排序。C语言编程代码如下:
#include <stdio.h>
#include <stdlib.h>
int partion(int R[ ], int low, int high) /*对数组R中的R[low]至R[high]间的记录进行一趟快速排序*/
{ int a = R[low]; /*将枢轴记录移至数组的闲置分量*/
while (low < high) /*从表的两端交替地向中间扫描*/
{ while (low<high&& R[high]>a)
high--;
if (low < high) /*将比枢轴记录小的记录移至低端*/
{ R[low] = R[high];
low++;
}
while (low < high&& R[low] < a)
low++;
if (low < high) /*将比枢轴记录大的记录移至高端*/
{ R[high] = R[low];
high--;
}
}
R[low] = a; /*将枢轴记录移至正确位置*/
return low; /*返回枢轴位置*/
}
void SwapSortB(int R[ ], int b, int c) /*对数组R中的全部记录按照递增顺序进行快速排序*/
{ int i;
if (b < c)
{ i = partion(R, b, c);
SwapSortB(R, b, i - 1);
SwapSortB(R, i + 1, c);
}
}
int main()
{
int r[11] = { 34546,110, 2, 3, 54, 5, 6, 27, 18, 9, 10 };
int b = 0;
int c = 10;
int i;
SwapSortB(r, b, c);
for (i = 0; i < 11; i++)
printf("%d,", r[i]);
printf("\n");
}
运行结果:
程序解说:
快速排序的算法是一个递归函数实例引入一对参数 b 和 c 作为待排序区域的上下界。在执行过程中,这两个参数随着区域的划分而不断变化。