实验3 内部排序算法比较

存储管理、查找和排序班级：软件101 姓名：xxx 学号：xxxxxx 完成日期：2011-12-15题目：内部排序算法比较一、需求分析...问题描述：通过随机数据比较各算法的关键字比较次数与移动次数。

基本要求：至少比较快速排序与堆排序。

对结果进行简单分析1)、通过随机数据比较各算法的关键字比较次数与移动次数，并对结果进行简单分析。

2)、测试数据：5、8、8、3、9、7二、概要设计...快速排序算法：void QSort (Re dType & R[], int s, int t ) {// 对记录序列R[s..t]进行快速排序if (s < t-1) { // 长度大于1pivotloc = Partition(R, s, t);// 对R[s..t] 进行一次划分QSort(R, s, pivotloc-1);// 对低子序列递归排序，pivotloc是枢轴位置QSort(R, pivotloc+1, t); // 对高子序列递归排序}} // QSort归并排序算法：void Me rge (RcdType SR[], RcdType &TR[], int i, int m, int n){// 将有序的记录序列SR[i..m] 和SR[m+1..n]// 归并为有序的记录序列TR[i..n]for (j=m+1, k=i; i<=m && j<=n; ++k){ // 将SR中记录由小到大地并入TRif (SR[i].key<=SR[j].key) TR[k] = SR[i++];e lse TR[k] = SR[j++];}… …} // Me rge三、详细设计...见附录：四、调试分析...1、通过课本程序调试，得出预期结果；2、了解了个种排序的时间复杂度，各种排序所需的比较次数，移动次数，在排序数比较小的情况下，排序时间都很短。

实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。

三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。

将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。

四、实验编程结果或过程：1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。

第三章内部排序算法比较3.1. 问题描述3.1.1 题目内容设计程序实现六种方法的内部排序：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

并对各个内部排序算法进行实测比较。

3.1.2 基本要求程序分别对六种常用的内部排序算法进行实测比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

待排序表的表长不小于100，其中数据要用随机数产生程序产生，要求用多组不同的输入数据进行比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次的移动）。

3.1.3 待测试数据因为所产生的数据是随机数，所以只需要用户输入要产生的随机数的个数。

所以可根据需要设置以下一组数：5，10，50，300，1000，7000，20000，50000。

3.2. 需求分析3.2.1 程序的基本功能首先用户输入要测试的随机数的个数，然后可以进行各个选项对数据进行不同的测试，程序能分别输出用起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序所用的移动关键字的步数，以便比较各个排序算法的效率。

3.2.2 输入值的形式和范围程序设定输入的整型数据在100000之内。

3.2.3 输出形式程序将产生的随机数以数组的形式储存，并在屏幕上依次输出，排序后得到的有序数组也同样依次输出，同时输出跟踪的来的总移动步数。

3.2.4 测试数据要求在调试时，为了能方便判断得出的结果是否正确可使用数量小的随机数，如3、4、5。

在调试确定算法能得出正确结果后测试数据要求每组随机数的个数应大于100，最好更长，这样才能更加容易得出各个排序算法在时间上的不同。

3.3. 概要设计3.3.1 主程序流程及模块调用关系（1）主程序流程图：一. 产生随机数。

二. 各个排序算法图 3-1 程序流程图（2）模块调用关系图见下页：图 3-23.3.2 核心的粗线条伪码算法设置一个类class Algorithm{……..将各个排序算法的函数作为类中的构造函数……..}A;Algorithm Sorting( )1. 输入随机数的个数N；2. 调用随机数产生函数产生个N随机数并储存到Array[1]~~Array[N]中.3. 输入选择功能4．switch(c){case '1':调用起泡法对所产生的随机数进行排序;case '2':调用直接插入法对所产生的随机数进行排序;case '3':调用简单选择法对所产生的随机数进行排序;case '4':调用快速排序法对所产生的随机数进行排序;case '5':调用Shell排序对所产生的随机数进行排序;case '6':调用堆排序对所产生的随机数进行排序;case '7':产生下一组随机数据case '8':结束并退出程序3.4. 详细设计3.4.1 实现概要设计的数据类型.定义一个类，将每个算法都现在该类中：Class Algorithm{Public:Bubblesort(){……….}StraightInsertsort(){……….}Selectsort(){……….}Quiksort(){……….}Shellsort(){……….}Heapesort(){……….}}A;3.4.2 每个操作的伪码算法.（1）.起泡法排序伪码算法：Algorithm BubbleSort( ){while(k>1){//i>1表明上一趟曾进行过记录交换设定一个记录最后一次交换位置的整型int lastExchangeIndex=1;for(int j=1;j<k;j++){作循环当后一个元素小于前一个时L.elem[j+1].key<L.elem[j].key{相互交换元素的值.记录交换的元素的位置}将一趟排序中无序序列中最后一个记录的位置传递给k,做下一次循环（2）.直接插入排序的伪算法：Algorithm InsertSort()for(int i=2;i<=L.length;++i)判断如果第i个元素的值小于第i-1元素的值时{ 需将第i个元素插入有序子表将i元素复制为哨兵for(int j=i-1;L.elem[0].key<L.elem[j].key;--j)将元素记录后移然后将哨兵插入到正确位置}（3）.Shell排序伪算法Algorithm ShellSort(){设置一个整型变量福初始值为5（dlta=5; ）{ 做运算dlta = dlta/3+1;调用ShellInsert函数}当设置的整型变量大于1;ShellInsert( ) //ShellInsert函数{for(int i=dk+1;i<=L.length;++i)if(L.elem[i].key<L.elem[i-dk].key){ //需将L.elem.[i]插入有序增量子表L.elem[0]=L.elem[i];//暂存在L.elem.[0]int j=i-dk;do{ L.elem[j+dk] = L.elem[j];j = j - dk;}while(j > 0&&L.elem[0].key < L.elem[j].key); //记录后移，查找插入位置插入操作L.elem[j+dk]=L.elem[0];}（4）. 快速排序伪算法：Algorithm QuikSort(){判断需要排序的数组长度，如果大于1{调用Partition函数，将Low 到Hight一分为二分别调用QSort函数，分别对高低子表进行递归排序} }Partition(sqlist &R,int low,int high) //划分函数{//对记录子序列R[low....high]进行一趟快速排序，并返回枢轴记录所在位置，//使得在它之前的记录的关键字均不大于它的关键字，在它之后的记录的关键//字均不小于它的关键字将枢轴记录移至数组的闲置地方；枢轴记录关键字；从表的两端交替地向中间扫描；将比枢轴记录小的记录移到底端将比枢轴记录大的记录移到高端枢轴记录移到正确位置（R.elem[low] = R.elem[0]）返回枢轴的位置return low}void QSort(sqlist &R,int low,int high) 函数对记录序列R[s....t]进行快速排序{ 如果子表长度大于1{ 调用Partition对R[s...t]进行一次划分，并返回枢轴位置对底端子序列递归排序(QSort(R,low,pivotloc-1) ).对高断子序列递归排序(QSort(R,pivotloc+1,high) ).}3.4.3 主程序和其它模块的伪码算法.Algorithm main( )1. 函数运行，并先后调用菜单函数和随机数产生函数2. 进入while循环，再次调用菜单函数3．进入如下一个Switch语句，对各个功能进行调用switch(c){ case '1':调用起泡法对所产生的随机数进行排序;case '2':调用直接插入法对所产生的随机数进行排序;……….case '6':调用堆排序对所产生的随机数进行排序;case '7':产生下一组随机数据case '8':结束并退出程序3.5. 调试分析3.5.1 设计与调试过程中遇到的问题及分析、体会在程序的最初调试中因为没有把握好各个函数之间的调用关系，因而出现了许多错误，比如得不到排序结果等，然后将所有排序的函数都写在了一个类中，这样，只要声明一次，以后就可以非常方便，准确的调用各个函数了。

数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。

内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。

本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

冒泡排序是一种简单直观的排序算法。

它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。

因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。

插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。

选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

以此类推，直到全部待排序的数据元素排完。

选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。

快速排序是一种分治的排序算法。

它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。

快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。

然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。

归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。