算法设计技能训练报告Word文件下载.docx

1、 node* head; int length;利用链表进行排序2.3算法设计1.直接插入排序原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。2.希尔排序又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。1.冒泡排序将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。设计交换判断条件，提前结束以排好序的序列循环2.快速排序不断寻找一个序列的中点，然

2、后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。1.直接选择排序将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。.堆排序利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。归并排序将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。测试图 4.1图 4.2图4.3结 论（1）平方阶（O（n2）排序 一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶（O（nlgn）排序 如快速、堆和归并排序；（3）O（n1+）阶排序 是介于0和1之间的常数，即0

3、1，如希尔排序；（4）线性阶（O（n）排序 如桶、箱和基数排序。各种排序方法比较 简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：待排序的记录数目n；记录的大小（规模）；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和辅助空间复杂度等。不同条件下，排序方法的选择（1）若n较小（如n50），可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。（2）若文件初始状

4、态基本有序（指正序），则应选用直接插人、冒泡或随机的快速排序为宜；（3）若n较大，则应采用时间复杂度为O（nlgn）的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后

5、的归并排序仍是稳定的。排序算法的稳定性1） 稳定的：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。 插入排序、冒泡排序、归并排序、分配排序（桶式、基数）都是稳定的排序算法。 2）不稳定的：否则称为不稳定的。 直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法 致 谢谢我的老师，他们严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；他们循循善诱的教导和不拘一格的思路给予我无尽的启迪。这片论文的每个实验细节和每个数据，都离不开你的细心指导。而你开朗的个性和宽容的态度，帮助我能够很快的融入我们这个新的实验室感谢我的同门，谢谢

6、你们给予我的帮助！感谢我的朋友，感谢你们在我失意时给我鼓励，在失落时给我支持，感谢你们和我一路走来，让我在此过程中倍感温暖！感谢我的家人我的父母、姐姐和弟弟。没有你们，就不会有今天的我！我一直感恩，感恩于我可以拥有一个如此温馨的家庭，让我所有的一切都可以在你们这里得到理解与支持，得到谅解和分担。我爱你们，爱我们的家！一个人的成长绝不是一件孤立的事，没有别人的支持与帮助绝不可能办到。我感谢可以有这样一个空间，让我对所有给予我关心、帮助的人说声“谢谢”！今后，我会继续努力，好好工作！好好学习！好好生活！参 考 文 献1 刘国钧，陈绍业，王凤翥.图书馆目录.第1版.北京：高等教育出版社，19572

7、傅承义，陈运泰，祁贵中.地球物理学基础.北京：科学出版社，1985，4473 华罗庚，王元.论一致分布与近似分析.中国科学，1973（4）：3393574 张筑生.微分半动力系统的不变集研究：学位论文，北京：数学系统学研究所，19835 Borko H，Bernier C LIndexing concepts and methods . New York: Academic Pr,19786机程序设计艺术英文名称：The Art of Computer Programming作者：Donald.E.Knuth7.计算机导论名称：Introduction to AlgorithmsThomas

8、H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford SteinC语言程序设计实用教程全面介绍了C语言的基础知识和程序设计方法，共分为三部分，由浅到深，再到综合应用。第一部分是基础知识的应用，包括第1章到第3章；第二部分为高级知识的应用，包括第4章到第7章；第三部分是综合应用，包括第8章。各章基本知识与典型例题及上机实训紧密结合，每章后面提供了大量的习题。为了满足国家计算机等级考试的要求，C语言程序设计实用教程介绍了Visual C+ 6.0的开发环境，教材内容涵盖了全国计算机等级考试考试大纲（C语言程序设计部分）。 C语言程序

9、设计实用教程可以作为高职高专各专业学生的教材，也可以作为普通高等院校各专业学生的教材，还可以作为全国计算机等级考试（二级C语言程序设计）的辅导wer by YOZOSOFT代码#includefstreamusing namespace std;time.hstdlib.h# define n 2000#define lj 20class MyListpublic: MyList（） head = NULL;/头指针为空 length = 0;/长度为0 MyList（） node* left = head; node* right = NULL; while （left != NULL） r

10、ight = left; left = left-next; delete right; void addNode（int user_index） if （isEmpty（） head = new node（）; head-next = NULL;index = user_index; else /创建一个新的节点 node* newnode = new node（）; newnode- /将节点添加到链表的最末端 node* t = head; while （t-next!=NULL） t = t- t-next = newnode; length+; int ljcode; int get

11、Length（） return length; void display（） if （isEmpty（） cout The list is empty!; return; node* temp = head; while （temp） cout index; if （!temp-next） /已至链表尾，可以结束输出了。 break;- temp = temp- cout 0; i-） addNode（i）; bool isEmpty（） if （head=NULL） return true; int ljcode=0; return false; void bubbleSort（） int

12、ljcode=1; /temp指针用来进行指向要交换的两个节点的左边一个 while （temp & if （temp-index next-index） exchangeNode（temp, temp-next）; /尾指针总是指向已经排好的元素的首地址，这里我们先移到链表尾部等待 node* tail = head; while （tail- tail = tail- /外层还是数组的思想，内层就是链表的思想了， /为什么外层要用数组的思想呢？因为这样比较简洁，不易搞错 for （int i = 0; i next != tail） exchangeNode（temp, temp- tai

13、l = temp; /交换相邻两个节点 void exchangeNode（node* left, node* right） /如果left是头结点 if （left=head） left-next = right- right-next = left; head = right; /找到左节点的前一个节点 node* before_left = head; while （before_left-=left） before_left = before_left- before_left-next = right; left-/堆的冒泡排序int ljcode2=0;void paixu（） M

14、yList hengbao; hengbao.lhInput（）; hengbao.display（）; hengbao.bubbleSort（）; int ljcode=0;void InsertionSort（int *a, int len） /插入排序函数 for （int j=1; j=0 & aikey） ai+1 = ai; i-; ai+1 = key;void ShellSort（int *a, int len） /希尔排序代码 int h = 1; while（ h0 ） for （int j=h; int key = aj; int i = j-h; while（ ikey

15、 ） ai+h = ai; i = i-h; ai+h = key; h = h/3;/冒泡排序void bubblesort（int *a,int len） int i,j; for（ i=0;len-1; for（ j=i+1;j=len-1;j+） if（aiaj） int t=ai; aj=ai; ai=t;/快速排序void quickSort（int s, int l, int r ） if （lr） int i = l, j = r, x = sl; while （i j） while（i = x） / 从右向左找第一个小于x的数 j-; if（i si+ = sj; si x）

16、 / 从左向右找第一个大于等于x的数 i+; sj- = si; si = x; quickSort（s, l, i - 1）; / 递归调用 quickSort（s, i + 1, r）;/选择排序void SelectSort（int *a, int len） for （int i=0; i int k = i; int key = ai; for （int j=i+1; if （ajai） largest = l; largest = i; if （ralargest） largest = r; if （largest! swap（ai, alargest）; MaxHeapify（a,

17、 largest, heapSize）;/ 创建最大堆void BuildMaxHeap（int *a, int len） for （int i=len/2-1;=0; MaxHeapify（a, i, len-1）;/ 堆排序void HeapSort（int *a, int len） BuildMaxHeap（a, len）; for （int i=len-1; swap（a0, ai）; MaxHeapify（a, 0, i-1）;/归并排序void merge（int *data, int p, int q, int r） int n1, n2, i, j, k; int *left=

18、NULL, *right=NULL; n1 = q-p+1; n2 = r-q; left = （int *）malloc（sizeof（int）*（n1）; right = （int *）malloc（sizeof（int）*（n2）; for（i=0;n1; i+） /对左数组赋值 lefti = datap+i; for（j=0;n2; j+） /对右数组赋值 rightj = dataq+1+j; i = j = 0; k = p; while（in1 &n2） /将数组元素值两两比较，并合并到data数组 if（lefti = rightj） datak+ = lefti+; els

19、e datak+ = rightj+; for（; i+） /如果左数组有元素剩余，则将剩余元素合并到data数组 datak+ = lefti; j+） /如果右数组有元素剩余，则将剩余元素合并到data数组 datak+ = rightj; void mergeSort（int *data, int p, int r） int q; if（p r） /只有一个或无记录时不须排序 q = （int）（p+r）/2）; /将data数组分成两半 mergeSort（data, p, q）; /递归拆分左数组 mergeSort（data, q+1, r）; /递归拆分右数组 merge（dat

20、a, p, q, r）; /合并数组 void output（int *A） ofstream output（c:textcode.txt,ios_base:out）; output数组元素如下：i+） Ai, output.close（）; ofstream output1（bincode.bin,ios:binary）; for（int i=0; output1, output1.close （）;int main（） int An; coutm; switch（m） case 1: InsertionSort（A,n）; output（A）; cout已经进行插入排序结果已存入文件 break; case 2: ShellSort（A, n） ;已经进行希尔排序 case 3: bubblesort（A,n）;已经进行起泡排序en