没有合适的资源？快使用搜索试试~ 我知道了~

文库首页开发技术其它算法设计与分析经典题目源代码！

算法设计与分析经典题目源代码！

算法设计与分析

经典题目源代码

需积分: 9 25 下载量 56 浏览量 2010-12-21 21:51:02 上传评论 2 收藏 274KB DOC 举报

温馨提示

试读

24页

这个文档里包含了算法设计与分析-C++语言描述（电子工业出版社出版）课程里需要做的典型实验题的源代码及实现，包括找零钱问题，0-1背包问题，比赛日程问题，找作案人问题，求数字排列问题等等，均是运用几种常用算法解决，如贪心法，蛮力法，分治法等等。绝对真实可用

资源推荐

资源详情

资源评论

定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排

序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结

合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况： +插入排

序

1、数组中的数据随机生成；

2、数组中的数据已经是非递减有序。

//SORT.H

#include <iostream>

using namespace std;

#include <ctime>

#include <cstdlib>

class Sort

{

public:

Sort(int [], int);

~Sort(){/****delete [] array;*****/};

int DataChoose();

void Data1(int [], int);

void Data2(int [], int);

void Swap(int &a, int &b);

int Partition(int [], int, int);

void QuickSort(int [],int);

void Quick(int [], int, int);

void InsertSort(int [], int);

void BubbleSort(int [], int);

void SelectSort(int [], int);

void Merge(int [], int, int, int);

void MergeSort(int [], int);

void RecMerge(int [], int, int);

void Print(int [], int);

private:

int arraysize;

};

Sort::Sort(int r[], int n)

{

if (n<0)

{

cerr << "** An invalid array size was entered." << endl;

exit (-1);

return;

}

arraysize = n;

int choice1 = DataChoose();

switch(choice1)

{

case 1:

//Sort::Data1(array, arraysize); //Switch 中函数调用?????

Data1(r, arraysize);

break; //break 别掉了!!!!

case 2:

//Sort::Data2(array, arraysize);

Data2(r, arraysize);

break;

default:

cerr << "**An invalid selection.**" << endl;

exit(-1);

}

int Sort::DataChoose()

{

int choice;

cout << "Enter the array to use:" << endl

<< "1、random" << endl

<< "2、non-descending" << endl

<< "What type (1 or 2): ";

cin >> choice;

cout << endl << endl;

return choice;

}

void Sort::Data1(int r[], int n) //时间种子随机产生数组

{

srand(time(0));

for (int i=0; i<n; i++)

{

r[i] = rand();

}

void Sort::Data2(int r[], int n) //1 到 num??????????????

{

for (int i=0,j=1; i<n; i++,j++) // i<=n 出错

{

r[i] = j;

}

void Sort::Swap(int &a, int &b) // 模板，都要标成 void Sort::Swap(T &a, T

&b)？

{

int temp = a;

a = b;

b = temp;

}

int Sort::Partition(int r[], int left, int right) //分划函数

{

int i=left, j=right+1;

do{

do i++; while(r[i]<r[left]);

do j--; while(r[j]>r[left]);

if (i<j) Swap(r[i],r[j]);

}while(i<j);

Swap(r[left], r[j]);

return j;

}

void Sort::QuickSort(int r[],int n)

{

Quick(r,0, n-1);

}

void Sort::Quick(int r[], int left, int right) //快速排序

{

if(left<right)

{

int j=Partition(r, left, right);

Quick(r, left, j-1);

Quick(r, j+1, right);

}

void Sort::InsertSort(int r[], int n) //添加一个插入排序

//靠，老出错。如果在 main()里改动态数组大小为 num+1 则出现负数。怎么解决？

{

int i,j;

for (i=2; i<=n; i++)

{

r[0] = r[i]; //设置哨兵

for (j=i-1; r[0]<r[j]; j--) //寻找插入位置

r[j+1] = r[j]; //记录后移

r[j+1] = r[0];

}

void Sort::BubbleSort(int r[], int n) //冒泡排序

{

int bound = n-1;

bool sorted = true;

{

sorted = true;

for(int j=0; j<bound; j++)

{

if(r[j] > r[j+1])

{

Swap(r[j],r[j+1]);

sorted = false;

}

bound--;

}while (!sorted);

}

void Sort::SelectSort(int r[], int n) //选择排序

{

int index;

for (int i=0; i<n-1; i++)

{

index = i;

for (int j=i+1; j<n; j++) //在无序区中选择最小记录

{

if (r[j] < r[index]) { index = j;}

Swap(r[index],r[i]);

}

//!!!!!把一个无序的数组拆成单个元素，排好序，然后再合并!!!!!

void Sort::Merge(int r[], int left, int mid, int right)

{

int *temp = new int [right-left+1];

int i=left, j=mid+1, k=0;

while((i<=mid)&&(j<=right))

if(r[i]<=r[j])temp[k++]=r[i++]; //有序合并到 temp 数组

else temp[k++]=r[j++];

while(i<=mid)temp[k++]=r[i++]; //若序列 2 全放入 temp 后序列 1 没完，

继续放入序列 1

while(j<=right)temp[k++]=r[j++];

for(i=0,k=left;k<=right; )

r[k++]=temp[i++]; //重新复制到 r[]中

}

void Sort::MergeSort(int r[], int n)

{

RecMerge(r, 0, n-1);

}

void Sort::RecMerge(int r[], int left, int right)

{

if(left<right)

{

int mid = (left+right)/2;

RecMerge(r, left, mid);

RecMerge(r, mid+1, right);

Merge(r,left,mid,right);

}

void Sort::Print(int r[], int n)

{

for (int i=0; i<n; i++) //输出自动换行

{

cout << r[i] << " ";

if ( (i+1)%10 == 0) cout << endl;

}

//SORT.CPP

#include <iostream>

using namespace std;

#include <ctime>

#include <cstdlib>

#include "Sort.h" //非递减有序是什么意思？

int SortChoose();

int main()

{

int num, choice2;

long start, end;

cout << "How many elements in the array? Input: ";

cin >> num;

//const int arraysize = 1000; //假设这个足够大的整形数组包含 1000 个元素.

const 变量只能在创建时初始化或者使用构造函数

int *array = new int [num];

//定义动态数组时不要掉了“ *”；并且动态分配的内存最后必须进行释放：

delete[]

Sort s(array, num);

剩余23页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

xiaoweiwei518

粉丝: 0
资源: 12

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

算法设计与分析经典题目源代码！

算法设计与分析的经典题目

算法设计与分析的经典问题

算法设计题集（经典问题分析）

计算机算法设计与分析例题代码

算法设计和分析题目和源代码.doc

算法分析与设计代码（全）

算法设计与分析（详细解析（含源代码））

算法设计与分析上机题目

算法设计与分析实验题目

计算机算法设计与分析-统计数字问题

ACM经典C++题目：Gone Fishing算法详解及源代码.doc

java经典算法源代码

50道算法经典剖析

ACM zoj题目 源代码

算法设计与分析 最近点对代码

算法设计与分析代码（java）

算法设计与分析课件与相关算法代码实现

算法分析与设计-赵端阳源代码与ppt

算法设计与分析（第二版）程序源码

算法设计与分析试题.docx

算法设计与分析（代码和实验报告）

简单的算法设计题目100道

算法设计与分析课程设计—内部排序（内含实验报告）

算法设计与分析课程设计

C语言经典算法100例（全）

数据结构经典编程代码

c语言100道经典程序题（题目和答案源码）

C语言经典算法100例

最新资源

ACM zoj题目源代码

算法设计与分析最近点对代码