while (j <= right) temp[k++] = l[j++];
for (i = 0, k = left; k <= right;)l[k++] = temp[i++];
}
void SortableList::Swap(int i, int j)
{
int c = l[i];
l[i] = l[j];
} while (i < j);
Swap(left, j);
return j;
}
源.app
#include<iostream>
#include"标头.h"
using namespace std;
void main()
{
int n = 10;
SortableList my1(n);
SortableList my2(n);
标头.h
#include<iostream>
using namespace std;
enum ResultCode {OutOfBounds,Success};
class SortableList
{
public:
SortableList(int mSize);
~SortableList();
void Input();
}
void SortableList::InsertSort(int left, int right)
{
for (int i = left+1; i <= right; i++){
int j = i;
int temp = l[i];
while (j > left && temp < l[j - 1]){
MergeSort(left, mid);
MergeSort(mid + 1, right);
Merge(left, mid, right);
}
}
void SortableList::Merge(int left, int mid, int right)
{
int *temp = new int[right - left + 1];
l[j] = l[j - 1]; j--;
}
l[j] = temp;
}
}
源.cpp
#include"标头.h"
void main()
{
int n = 10;
int x = 4;
SortableList myl(n);
myl.Input();
myl.Select(x,4);
myl.Output();
}
实验学时
2
实验时间
2017-3-30
一、实验目的和任务
理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法 的算法原理及实现过程的理解
二、实验环境(实验设备)
Visual Studio 2015
三、实验原理及内容（包括操作过程、结果分析等）
一、用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排 序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。
int Select(int k,int left,int right,int r);
};
SortableList::SortableList(int mSize)
{
maxSize = mSize;
l = new int[maxSize];
n = 0;
}
SortableList::~SortableList(){delete[]l;}
标头.h
#include<iostream>
using namespace std;
class SortableList
{
public:
SortableList(int mSize);
~SortableList();
void Input();//输入数组
void Output();//输出数组
void MergeSort();//两路合并排序
void SortableList::QuickSort(){ QuickSort(0, n - 1); }
void SortableList::MergeSort(int left, int right)
{
if (left < right){
int mid = (left + right) / 2;
}
for (int i = 1; i <= n / r; i++)
{
InsertSort(left + (i - 1)*r, left + i*r - 1); //二次取中规则求每组的中间值
Swap(left + i - 1, left + (i - 1)*r + (int)ceil((double)r / 2) - 1); //将每组的中间值交换到子表前部集中存放
cin >> l[i];
if ([i] == -1)
break;
n++;
}
}
void SortableList::Output()
{
for (int i = 0; i < n; i++)
cout << l[i] << " ";
}
void SortableList::MergeSort(){ MergeSort(0, n - 1); }
l[j] = c;
}
void SortableList::QuickSort(int left, int right)
{
if (left < right){
int j = Parition(left, right);
QuickSort(left, j - 1);
QuickSort(j + 1, right);
void QuickSort();//快速排序
private:
int *l;//数组指针
int maxSize;//数组最大长度
int n;//数组已有元素个数
void MergeSort(int left, int right);
void Merge(int left, int mid, int right);
void Output();
ResultCode Select(int &x, int k);
private:
int *l;
int maxSize;
int n;
void Swap(int i, int j);
void InsertSort(int left, int right);
int Partition(int left, int right);
l = new int[maxSize];
n = 0;
}
SortableList::~SortableList(){delete[]l;}
void SortableList::Input()
{
cout << "请输入待排序的数组\n";
for (int i = 0; i < maxSize; i++){
int i = left, j = mid + 1, k = 0;
while ((i <= mid) && (j <= right))
if (l[i] <= l[j]) temp[k++] = l[i++];
else temp[k++] = l[j++];
while (i <= mid) temp[k++] = l[i++];
}
ResultCode SortableList::Select(int &x, int k)
{
if (n <= 0 || k > n || k <= 0)return OutOfBounds;
int j = Select(k, 0,n - 1, 5);
x = l[j];
return Success;
实 验 报 告
（2016/2017学年 第二学期）
课程名称
算法分析与设计
实验名称
分治策略
实验时间
2017
年
3
月
30
日
指导单位
计算机学院 软件工程系
指导教师
张怡婷
学生姓名
霍淇滨
班级学号
B15041236
学院(系)
计算机学院
专 业
软件工程
实 验 报 告
实验名称
分治策略
指导教师
张怡婷
实验类型
验证型（第4个实验密码算法是“设计型”）
{
int i = left, j = right + 1;
do{
do i++; while (l[i] < l[left]);
do j--; while (l[j] > l[left]);
if (i < j) Swap(i, j);
} while (i < j);
Swap(left, j);