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

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

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

算法设计与分析

经典题目源代码

需积分: 9 25 下载量 155 浏览量更新于2023-07-05 评论 2 收藏 274KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

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页未读，继续阅读

xiaoweiwei518

粉丝: 0
资源: 12

上传资源快速赚钱

我的内容管理收起

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

会员权益专享

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

评论0

会员权益专享

最新资源

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

评论0

七个完整rbf算法源程序

算法设计与分析案例

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

算法设计与分析

算法设计与分析的起源

算法设计与分析：常见排序算法详解

算法设计与分析：揭开算法的奥秘

算法设计与分析：算法伪码表述技巧

算法设计与分析经典题目

算法设计与分析课程设计csdn

吉林大学算法设计与分析csdn

算法设计与分析习题解答(第4版)pdf

算法设计与分析学习与反思

中科大算法设计与分析复习资料csdn

nefu算法设计与分析课程设计

算法设计与分析屈婉玲pdf

广州大学算法设计与分析期末试卷 csdn

算法设计与分析中科大csdn试卷

屈婉玲算法设计与分析第二版pdf

计算机算法设计与分析 陈玉福 pdf

会员权益专享

最新资源

计算机算法设计与分析陈玉福 pdf