文档介绍：算法分析与设计实验报告--分治法
《算法分析设设》设设设告与
完成日期,、设设目的
(1)了解分治策略算法思想
(2)掌握快速排序、设排序算法并
(3)了解其他分治设设典型算法
二,设设容,内
(1)设一设设的程序～设设设排序。写个并
(2)设一段程序～设设快速排序。写
(3)设程序设设循设设日程表。设有写n=2k个运网个设设要设行球循设设。设要设设一设足
以下要求的比设日程表,;1,每设手必设其个与它n-1个设手各设一次;2,每设手一天只能设一设;个3,循设设设行n-1天
三,设设要求,
;1,写并运出源程序～设设设行
;2,设设设设程序设设及行设果运
四,算法思想分析,
?设排序,待排序元素分成大小大致相同的集合～分设把设并将两个两个
子集合设行排序～最设排序的子集合合成设所要求的排好序的集合将号并
?快速排序,通设一次排序要排序的据分割成立的部分～其中一将数独两
部分的所有据比外一部分的所有据都要小～然后再按此方法设设数另数两
部分据分设设行快速排序～整排序设程可以设设设行～以此到整据设数个达个数
成有序序列。
?按照分治策略～所有设手分设设～将两n个设手的比设日程就可以通设设n/2个设手设设的比设日程表定。设设的设设手设行分割～直到剩下设手设～比设来决两个
日程表的制定就设得常设设。设设只要设设设手设行比设就可以了异两个
五,算法源代设,
?设排序,并
源代设如下,
#include<iostream>
using namespace std;
void merge(int array[], int p, int q, int r)
{ int i,k;
int begin1,end1,begin2,end2;int* temp = new int [r-p+1]; //申设空设～使其大小设已设排序序列之和～设空设用存放合后、两个来并/
/的序列
//设定指设～最初位置分设设已设排序序列的起止位置两个两个
begin1= p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2))
{
if(array[begin1]<array[begin2]){
temp[k] = array[begin1];
begin1++;
}
else
{
temp[k] = array[begin2];
begin2++;
}
k++;
}
//若第一序列有剩余～拷设出粘到合序列尾个来并
while(begin1<=end1)
temp[k++] = array[begin1++];//若第二序列有剩余～拷设出粘到合序列尾个来并
while(begin2<=end2)
temp[k++] = array[begin2++];for (i = 0; i < (r - p +1); i++) //将数排序好的序列拷设回设中
array[p+i] = temp[i];
delete[] (temp);
}
void merge_sort(int data[], int left, int right)
{
if(left< right)
{
int mid = (left+ right) / 2;
merge_sort(data, left, mid);
merge_sort(data, mid+1, right);
merge(data, left, mid, right); }
}
int main()
{
int a[8]={10,8,98,56,42,40,7,5};
merge(a,0,3,7);
merge_sort(a,0,7);
cout<<"设排序后的设设,并数"<<endl;
int z=0;
for (z;z<8;z++)
{
cout<<a[z]<<" ";
}
cout<<endl;
return 0;
}
截设如下,
,
算法设设代设如下,
#include <iostream>using namespace std;void quicksort(int number[], int left, int right)
{
int i, j, s;
if(left < right) {
s = number[(left+right)/2];
i = left - 1;
j = right + 1;
while(1)