算法分析与设计实验报告 CQUPT

计算机科学与技术学院

算法分析与设计 实验报告

目录

实验报告一排序问题求解 ..................................................................................................................... 2 实验报告二背包问题求解 ..................................................................................................................... 8 实验报告三最短路径求解 ................................................................................................................... 12 实验报告四 N-皇后问题求解 ...................................................................................................... 18

姓名：XXX学号：XXXXXXXX班级：XXXXXXX

实验报告一 排序问题求解

实验目的

1）以排序（分类）问题为例，掌握分治法的基本设计策略。 2）熟练掌握一般插入排序算法的实现； 3）熟练掌握快速排序算法的实现； 4) 理解常见的算法经验分析方法；

实验内容与步骤 1. 生成实验数据.

要求：编写一个函数datagenetare，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。 2. 实现直接插入排序算法. 要求：实现insertionsort算法。

算法的输入是data.txt；

输出记录为文件：resultsIS.txt；同时记录运行时间为TimeIS。 3. 实现快速排序算法. 要求：实现QuickSort算法。

算法的输入是data.txt；

输出记录为文件：resultsQS.txt；同时记录运行时间为TimeQS。

算法的基本思想

直接插入排序：

假设待排序的 n 个记录{R0，R1，…，Rn}顺序存放在数组中，直接插入法在插入记录 Ri(i=1，2，…，n-1)时，记录被划分为两个区间[R0,Ri-1]和[Ri+1,Rn-1],其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki 与 Ki-1Ki-2，…，K0 依次比较，找出应该插入的位置，将记录 Ri 插，然后将剩下的 i-1 个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过 i-1 趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

快速排序：

快速排序是基于分治模式的。假设待排序数组 A[p..r]。①分解：数组 A[p..r]被划分成两个（可能空）子数组 A[p..q-1]和 A[q+1..r],使得 A[p..q-1]中的每个元素都小于等于

A(q)，而且，小于等于 A[q+1..r]中的元素。小标 q 也在这个划分过程中进行计算。②解决：通过递归调用快速排序，对子数组 A[p..q-1]和 A[q+1..r]排序。③合并：因为两个子数组是就地排序的，将它们合并不需要操作：整个数组A[p..r]已排序。 算法实现

（1）直接插入排序：

void insert_sort(ElemType a[],int n)

//待排序元素用一个数组a表示，数组有n个元素 { int i,j; ElemType t;

for ( i=1; i

while ((j>=0)&& (t

{ a[j+1]=a[j]; j--; } // 顺序比较和移动 a[j+1]=t;} }

直接插入排序的时间复杂度为O（n2）

（2）快速排序： void QuickSort(SqList *list){ }

void Qsort(SqList *list,int low,int hight){

if( low< hight){

//数组从下表为1开始有效，下表为0的单元做哨兵初值为0 Qsort(list,1,list->length-1);

int mid =0;

mid = partition(list,low,hight);

}//end if

Qsort(list,low,mid-1); //对左边的无序数列进行排序 Qsort(list,mid+1,hight); //对右边的无序数列进行排序

}

int partition(SqList *list,int low,int hight){ ElemType mid = list->array[low];

while(low< hight){

while(low< hight && list->array[hight] >= mid)

{ }

swap(list,low,hight);

while(low< hight && list->array[low] <= mid) { }

swap(list,low,hight);

low++; hight--;

}//end out while

return low; }

void swap( SqList *list,int low,int hight){

ElemType temp = 0; temp = list->array[low];

list->array[low] = list->array[hight]; list->array[hight] = temp;

}

快速排序的时间复杂度是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。

三、程序流程图

1. 直接插入排序程序流程图