分治算法（实现求最大最小值和快速排序）

实验一分治算法 一、实验目的

1)掌握分治算法的设计思想与分析方法， 2)能够按题目要求编程实现分治算法。 二、方法原理

将一个规模为n的原问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；递归地求解这些子问题，然后将子问题的解合并为原问题的解。

三、实验设备

PC机一台，C语言、PASCAL语言、Matlab任选 四、掌握要点

将原问题分解为若干规模较小、互相独立、与原问题形式相同的子问题；求解子问题；将子问题的解合并为原问题的解。

五、实验内容

1)采用分治算法求10个实数{ 9,3,6,2,1,8,4,5,7,23 }序列中的最大元素和最小元素，并分析算法的时间复

杂度。

2)编程实现：采用分治算法方法实现快速排序算法。要求：输入数组为{9,4,6,2,5,8,4,5,6,22 }；限定数组

排序范围；输出显示为递增顺序排序的数组。 六、实验要求

1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法；

2)编写上机实验程序，作好上机前的准备工作；

3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）；

4)分析和解释计算结果； 5)按照要求书写实验报告；

源代码：

1.分治算法求10个实数{ 9,3,6,2,1,8,4,5,7,23 }序列中的最大元素和最小元素

#include #include

int* getmaxmin(int a, int b) { int* t = new int[2];//动态 if (a < b) { t[0] = a; t[1] = b; } else { t[0] = b; t[1] = a; } return t; }

int * maxmin(int a[], int low, int high) { if (high - low <= 1) { int* t = new int[2];

return getmaxmin(a[low], a[high]); } else {

int mid = (high + low) / 2; int* m1 = maxmin(a, low, mid); int* m2 = maxmin(a, mid + 1, high);

printf(\"前半部分得到的值：%d, %d\\n\printf(\"后半部分得到的值：%d, %d\\n\int*r= new int[2]; if (m1[0] < m2[0]) {

r[0] = m1[0]; } else { r[0] = m2[0]; }

if (m1[1] < m2[1]) { r[1] = m2[1]; } else { r[1] = m1[1]; } return r; } }

int main() {

int a[10] = { 8,3, 6, 2, 1, 8, 4, 5, 7,23 }; int* r = maxmin(a, 0, 9);

printf(\"最大值为：%d，最小值为：%d\\n\system(\"pause\"); } 结果：

2.采用分治算法方法实现快速排序算法 #include #include

void swap(int &x, int &y) { int t; t = x; x = y; y = t; }

int divide_and_conquer(int a[], int low, int high) {//按枢点元素划分序列int split int k, i = low;

int x = a[low];

for (k = low + 1; k <= high; k++) { if (a[k] <= x) { i += 1;

if (i != k)swap(a[i], a[k]); } }

swap(a[low], a[i]); return i; }

void quick_sort(int a[], int low, int high) { int k;

if (low < high) {

k = divide_and_conquer(a, low, high); quick_sort(a, low, k - 1); quick_sort(a, k + 1, high); } }

void main() {

int a[] = { 9,4,6,2,5,8,4,5,6,22 }; quick_sort(a, 0, 9); for (int i = 0; i < 10; i++) printf(\"%d \system(\"pause\"); } 结果：