下载文档原格式
需求分析报告排序算法的实现与演示系统班级 10060342X第十组姓名崔杰 43郭伟 51刘文忠 50付耀萱 48一．问题的提出1.1概述排序在人们的日常生活和学习、科研、生产等各个方面有着重要的应用。
因此掌握常用的排序算法是很必要的。
此次设计拟开发一个排序算法演示系统，以提高对排序算法的掌握程度。
本系统实现八种不同排序算法即：快速排序、冒泡排序、堆排序、直接插入排序、希尔排序、直接选择排序、归并排序、基数排序的排序演示。
用户可以选择排序算法以演示输入数据在该排序算法下的排序过程。
1.2设计的意义随着计算机技术的发展，各种排序算法不断的被提出。
排序算法在计算机科学中有非常重要的意义，且应用很广泛。
在以后的发展中排序对我们的学习和生活的影响会逐渐增大，很有必要学习排序知识。
因此此次毕业设计一方面使自己掌握排序的知识，另一方面锻炼一下独立开发系统的能力。
二．设计目的内容和要求2.1设计的目的《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。
进行数据结构课程设计要达到以下目的：1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
2.2设计内容和要求设计内容：1.实现各种内部排序。
包括直接插入排序，冒泡排序，直接选择排序，希尔排序，快速排序，堆排序，归并排序。
2.待排序的元素的关键字为整数或（字符）。
可用随机数据和用户输入数据作测试比较。
比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。
3.演示程序以人机对话的形式进行。
《程序设计实践》报告学号江元；姓名 090241111 ；题目序号 2011年题目：排序7.1B类的第5题；难度等级 B一、题目写出快速排序的非递归算法二、问题分析及求解基本思路问题分析：快速排序是对冒泡排序的一种改进。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
而在程序设计中虽然应用递归技术, 能够使得程序简洁易懂, 但是效率并不是最高的,因此可以利用栈结构实现非递归的快速排序。
求解基本思路：将每次分治的两个序列的高位和低位入栈，每次都从栈中获取一对高位和低位，分别处理。
处理过程是：选取高位作为基准位置，从低位开始向高位遍历，如果比基准元素小，那么和第i个交换，如果有交换，那么i++，等一遍遍历完成后，如果i 的位置不等于基准位置，那么所选的基准位置的值不是最大的而这时候i的位置之前的元素都比基准值小，那么i的位置应该是基准值，将i所在位置的值和基准位置进行交换。
这时候，在i的左右就将序列分成两部分了，一部分比i所在位置值小，一部分比i所在位置值大的，然后再次将前面一部分和后面一部分的高位和低位分别入栈，再次选择基准位置，直到所选择的区间大小小于2，就可以不用入栈了。
三、问题求解的整体框架结构四、主要算法1．非递归快速排序算法qsrt( a, l , r )：由partition(pData, low, high)返回了轴值，st.push(low); st.push(pivot - 1); st.push(pivot + 1); st.push(high);循环执行下列语句直到栈为空（1）high = st.top(); st.pop(); low = st.top(); st.pop();（2）若满足low < high ，调用 partition(pData, low, high)返回轴值; 定义tmp = pivot -1若low < tmp ，st.push(low); st.push(tmp);tmp = pivot + 1;若tmp < high ，st.push(tmp); st.push(high);2．算法时间和空间复杂度：时间复杂度：最坏情况下时间代价为T(n)=O （n*n ）,最好情况下时间代价为O （nlogn ）,平均时间代价也为O（nlogn）。
《排列问题》教学设计一、教学目标1．在“4人排队照相，有几种排法”的问题情境中，掌握解决“排列问题”的方法，体会解决问题策略的多样性。
2．通过摆一摆、写一写、说一说、想一想等活动，发展观察、分析及推理能力，训练思维的有序性，渗透数形结合的思想方法。
3．借助排队照相排队唱歌等生活情境，经历数学规律的形成过程，感受数学与生活的密切联系。
二、教学重难点：1.掌握解决“排列问题”的方法，培养学生思维的有序性。
2.探究事物的排列规律。
三、教具准备：多媒体课件、学具卡片。
四、学具准备：学具卡片、自主学习记录单。
课前交流：同学们，很高兴今天能和你们一起探讨有趣的数学问题，希望在本节课中同学们能做到乐于倾听，勇于发言，有没有信心完成本节课的任务？五．教学过程一、创设数学情境，提出数学问题师：同学们，你们喜欢外出游玩吗？见到一处美景，你们会才用什什么方式留念呢？（拍照）同学们看大屏幕，小刚、小华、小平、小冬四位小朋友也去游玩了，他们也采用照相的方式合影留念了。
（课件）请大家大胆猜测一下，如果他们四人排成一行照相，会有几种不同的排法呢？生可能：4种、6种、12种……（师板书结果）二、组织有效教学，探究数学本质1、确定研究思路师：相信同学们都有了自己的想法，其实这是一个很有趣的数学问题。
既然是数学问题，就有其内在的规律和方法等着我们去探究发现，大家有信心吗？（生：有）今天我们就借助照相问题来一起走进对“排列问题”的研究。
（板书：排列问题）师：既然是排列，就一定和人数的多少有关系。
大家想一想，如果要探究其中的规律和方法，我们应该先选择多少人来进行研究比较合适呢？预设：生可能1：1人。
生可能2：2人。
生可能3：先从人数少的情况开始研究，然后再研究人数多的情况。
师总结：也就是说先研究人数比较简单的，再研究人数比较复杂的，这其实是我们数学学习中常用的一种研究方法——化繁为简（教师板贴），今天我们就用这种方法来研究排列问题。
2、研究两人的排列问题师：下面我们就采用这位同学的提议，先来研究两人排列照相的情况，好不好？我们就以小刚和小华为例来进行研究，如果这两人排成一行照相，会有几种不同的排法呢？（课件出示小刚和小华的名字卡片）生可能1：两种：小刚、小华；小华、小刚。
快速排序算法实验报告《快速排序算法实验报告》摘要：本实验通过对快速排序算法的理论分析和实际测试，验证了快速排序算法在处理大规模数据时的高效性和稳定性。
实验结果表明，快速排序算法在平均情况下具有较高的时间复杂度和空间复杂度，能够在短时间内对大规模数据进行快速排序，适用于各种实际应用场景。
1. 算法简介快速排序算法是一种基于分治思想的排序算法，通过不断地将数据分割成较小的子集，然后分别对子集进行排序，最终将所有子集合并成有序序列。
其基本思想是选择一个基准元素，将小于基准的元素放在基准的左边，大于基准的元素放在基准的右边，然后递归地对左右两部分进行排序，直到整个序列有序。
2. 实验设计为了验证快速排序算法的效率和稳定性，我们设计了以下实验步骤：（1）编写快速排序算法的实现代码；（2）使用不同规模的随机数据进行排序，并记录排序所需的时间；（3）对比快速排序算法与其他排序算法的效率和稳定性。
3. 实验结果我们使用C++语言编写了快速排序算法的实现代码，并对不同规模的随机数据进行了排序实验。
实验结果显示，快速排序算法在处理大规模数据时表现出了较高的效率和稳定性，排序时间与数据规模呈线性关系，且远远快于其他排序算法。
此外，快速排序算法在最坏情况下的时间复杂度为O(n^2)，但在平均情况下的时间复杂度为O(nlogn)，具有较好的性能表现。
4. 结论通过实验验证，我们得出了以下结论：（1）快速排序算法在处理大规模数据时具有较高的效率和稳定性；（2）快速排序算法在平均情况下具有较高的时间复杂度和空间复杂度，适用于各种实际应用场景；（3）快速排序算法在最坏情况下的时间复杂度为O(n^2)，需要注意避免最坏情况的发生。
综上所述，快速排序算法是一种高效且稳定的排序算法，能够在短时间内对大规模数据进行快速排序，适用于各种实际应用场景。
在实际开发中，我们应该充分利用快速排序算法的优势，并注意避免最坏情况的发生，以提高算法的效率和稳定性。
实验报告一、实验目的在计算机科学与数学中，排序算法是一种基本并且常用的算法，一个排序演算法是一种能将一串资料依照特定排序方式的一种演算法。
有效的排序演算法在一些演算法中是重要的，如此这些演算法才能得到正确解答。
排序演算法也用在处理文字资料以及产生人类可读的输出结果。
由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
通过实现相关一些排序算法，加深对于算法知识的理解与学习。
二、实验题目要求实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法，并比较这些算法的性能。
三、实验要求（一）在随机产生的空间大小分别为N = 10，1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。
（二）结果输出:1） N=10时，排序结果。
2） N=1000，10000，100000时，对同一个样本实例，不同排序完成所需的时间。
3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。
四、实验内容各种排序算法相关代码的实现及其原理说明如下：1.合并排序对于合并排序，算法过程说明如下：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。
合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕，此时将另一非空的子文件中剩余记录依次复制到R1中即可。
2.插入排序关于直接插入排序的算法说明如下：假设待排序的记录存放在数组R[1..n]中。
《排序工作量》解题报告
总体来说比较简单，考察的方向是“分治”法的应用。
《排序工作量》问题实质上就是求出一列数中的“逆序对”。
所谓“逆序对”就是指数的大小与其在序列中的顺序相反的一对数。
例如：<3,4,2,1,3>中“逆序对”有<3,2>,<3,1>,<4,2>,<4,1>,<4,3>这5个。
如果不仔细分析，可以得出如下的方法，也是最基本的方法：
对于每个数Ai，考察A(i+1)至An中大于Ai的个数。
具体如下：
tot:=0;
For I:=1to n do
For j:=I+1to n do
If A[j]>A[I]then
Inc(tot);
Return(tot);
这个算法的效率如何呢？其时间复杂度为O(N^2)，对于本题，N最大为10000，显然运行的时间过长。
那么，如何在较快的时间内求出“逆序对”的数目呢？
上面的算法慢在分析Ai时没有利用A1至A(i-1)的分析结果，如果，我们在分析Ai时同时分析了A1至A(I-1)，那么时间就一定会提高。
于是，得出了一个与“归并排序”十分类似的方法。
我将数组A划分为两部分，A[1..i]与A[I+1..N]，然后分别求各部分的“逆序对”，同时将各部分排序，然后将左右两部分的结果“综合利用”，在O(N)的时间内求出左部分相对于右部分的“逆序对”，再将这些值加起来，就为整个的“逆序对”数目。
具体算法如下：
Function Sort(Var A:Array[1..N]of Real;L,R:Integer):Integer;
{这个函数返回A数组A[L..R]中“逆序对”的数目，并对A[L..R]排序}
Begin
IF L<R Then
Begin
T:=(L+R)Div2;
P1:=Sort(A,L,T);
P2:=Sort(A,T+1,R);
P3:=Merge(A,L,T,R);
Sort:=P1+P2+P3;
End;
End;
Function Merge(Var A:array[1..N]of Real;L,T,R:Integer):Integer;
{这个函数是将A数组已经排好序的两部分综合在一起，并求出左部分相对于右部分的“逆序对”数目}
Begin
I:=L;J:=T+1;P:=0;W:=L-1;
While(I<=T)and(J<=R)Do
If A[I]<A[J]Then
Begin
Inc(w);
B[w]:=A[I];
Inc(P,J-T);
Inc(I);
End
Else
Begin
Inc(w);
B[w]:=A[J];
Inc(j);
End;
While I<=T Do
Begin
Inc(w);
B[w]:=A[I];
Inc(P,J-T);
Inc(I);
End;
While J<=R Do
Begin
Inc(w);
B[w]:=A[j];
Inc(j);
End;
Merge:=P;
A[L..R]:=B[L..R];
End;
这个算法本身属于分治法，时间复杂度为O(N lgN)，显然比上一个算法较优些。
其原因在M erge函数中“逆序对”的累加（P值的改变）是跳跃的，其跳跃的基础在于左、右两部分已经排好序了。
这个题目虽然比较简单，但如果不加思考，盲目去做，得分不会很高。
这个题目体现了分治法的时间效率。
如果对这个题目进行仔细思考，收获还是很大的。
注：两个算法对测试数据的执行情况见测试数据说明。
Const
Max=10000;{数组界限}
Fin='Sort.Inp';{输入文件名}
Fou='Sort.Out';{输出文件名}
Type
Zis=array[1..max]of Real;{数组类型说明}
Var
Tot:longint;{“逆序对”总数}
N:integer;{数组大小}
Zi,Use:^zis;{记录数列的数组}
F:Text;{文件变量说明}
Procedure Init;{初始化过程，输入数据}
Var
i:integer;
Begin
New(zi);
New(use);
Assign(f,fin);
Reset(f);
Readln(f,n);
For i:=1to n do
read(f,zi^[i]);
Close(f);
end;
Procedure Sort(l,R:integer);{利用归并排序求“逆序对”}
Var
T:integer;
Procedure Merge(l,t,r:integer);
{将两个排好序的数组“归并”在一起，同时求出左部分相对于右部分“逆序对”
的数目}
Var
i,j,k:integer;
Begin
i:=l;
j:=T+1;
k:=l-1;
While(i<=t)and(j<=r)do
Begin
if zi^[i]<zi^[j]then
Begin
inc(tot,j-t-1);{跳跃累加“逆序对”数目}
inc(k);
use^[k]:=zi^[i];
inc(i);
end
Else
Begin
inc(k);
use^[k]:=zi^[j];
inc(j);
end;
end;
while i<=t do{剩余部分的尾处理}
Begin
inc(k);
use^[k]:=zi^[i];
inc(i);
inc(tot,r-t);
end;
while j<=r do
Begin
inc(k);
use^[k]:=zi^[j];
inc(j);
end;
Move(use^[l],zi^[l],(r-l+1)*6);{返回两个数组的归并后的排序数组}
end;
Begin
if l<r then
Begin
t:=(l+r)div2;{“分”}
Sort(l,t);{“分”部分“治”}
Sort(t+1,r);
Merge(l,t,r);{“合”}
end;
end;
Procedure Print;{输出结果}
Begin
Assign(F,fou);
rewrite(f);
Writeln(f,tot);
Close(f);
end;
Begin{主过程}
Init;{输入数据}
Tot:=0;
Sort(1,n);{求解}
Print;{输出结果}
end.。
