南邮数据结构上机实验四内排序算法的实现以及性能比较

2.1 直接插入排序假设待排序的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趟排序后即成为有序序列。

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

2.1.2排序过程初始数据：10 3 25 20 8第一趟：[ 3 10 ] 25 20 8 （将前两个数据排序）第二趟：[ 3 10 25] 20 8 （将25 放入前面数据中的适当位置）第三趟：[ 3 10 20 25 ] 8 （将20 放入适当的位置）第四趟：[ 3 8 10 20 25 ] （将8 放入适当的位置）2.1.3时间复杂度分析直接插入排序算法必须进行n-1趟。

最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。

因此最好情况下的时间复杂度就是O(n)。

最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。

2.2 直接选择排序待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。

第一趟第n个记录中找出关键码最小的记录与第n个记录交换；第二趟，从第二个记录开始的，2 -1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i 趟，则从第i个记录开始的n - i + l个记录中选出关键码最小的记录与第i 个记录交换，直到所有记录排好序。

实验题目：各种查找及排序算法比较实验内容：内部排序算法——插入排序（直接插入排序、折半插入排序）、交换排序（冒泡、快速排序）、选择排序（直接选择排序、堆排序）和归并排序（2-路归并排序）的具体实现。

目的与要求：掌握各种内部排序算法的特点，并对一整型数组排序，比较不同算法的速度。

实验算法：1）、数据结构描述：主函数中的a数组保存需要排序数组，将数组作为自变量输入到各种排序算法的函数中，各个函数返回值为排序之后的数组，在主函数中以一个循环体输出。

2）、函数和算法描述：主函数main先用循环体保存数组a，然后输出菜单，通过switch语句调用排序函数，将数组排序后输出。

InsertSort为直接插入排序对应的函数，并附有插入元素到数组的功能，函数主体是从数组第二个元素开始与其前的元素一一比较大小，并且插入到合适位置使得该元素的大小位于相邻元素之间。

BinsertSort为折半插入排序对应的函数，函数主体是在如上所述进行插入时，先比较待插入元素与其前的有序列的中心元素的大小关系，以此循环来判断插入位置。

BubbleSort为冒泡排序对应的函数，为二重循环结构，外循环每循环一次，决定出待排序部分的最大值并置于待排部分的末端，内循环对相邻两个元素大小作比较，进行调换。

Partition QuickSort为快速排序对应的函数，建有两个指针，从待排部分两端进行扫描，一次循环之后，将极大值和极小值各置于一端。

SelectMinKey SSSort为选择排序对应的函数，每循环一次，直接选出待排序部分中最小的元素并置于已排序部分之后，直至待排部分长度为0。

Merge MSort MergeSort为归并排序对应的函数，先将数组元素每两个一组并在组内排序，再将每两组和为一组进行排序，依次循环，直至分组长度与数组长度相同。

HeapAdjust HeapSort为堆排序对应的函数，通过循环，将数组调整为大顶堆形式，输出一次即可得到有序序列。

数据结构课程设计报告题目：各种内排序性能比较学生姓名：学号：班级：指导教师：2011-6-13目录1、需求分析说明 (2)1.1所需完成的任务及要求1.2程序实现的功能2、总体设计 (3)2.1 总体设计说明2.2 总体流程图2.3各主程序详细流程图3、详细设计 (7)3.1使用的算法思想3.2各个算法的效率简析4、实现部分 (8)4.1程序算法的代码5、程序测试 (15)5.1程序运行的主界面5.2 各算法运行界面6、总结 (18)1、需求分析说明排序是数据处理中经常遇到的一种重要操作。

然而排序的算法有很多，各有其优缺点和使用场合。

本程序的设计的主要目的是通过比较各种内部排序（包括：插入法排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。

达到在实际应用中选择合适的方法消耗最短的时间完成排序。

1.1所需完成的任务及要求任务：1)用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；2)输入的数据形式为任何一个正整数，大小不限。

要求：排序后的数组是从小到大的；1.2程序实现的功能（1）使用随机函数实现数组初始化，生成多组元素个数不同的数组；（2）用列表打印出每种排序下的各趟排序结果；（3）打印使用各种排序算法以后元素比较和交换的次数；（4）设计合理的打印列表来打印。

2、总体设计（从总体上说明该题目的框架，用文字和图表说明）2.1 总体设计说明采用插入气泡，选择，快速，合并的方法实现各种排序算法，并且在实现过程中插入适当变量来实现计数元素交换次数和比较次数的统计。

对于每一趟比较之后元素顺序以及最后的结果使用单独的函数来实现，形成单独的一个模块；2.2 总体流程图2.3 各主程序详细流程图①主函数流程图：3、详细设计3.1 使用的算法思想（1）对主界面的menu菜单，在主函数里面用switch语句调用各个模块的功能调用；（2）在插入法时，其算法思想是：将第一个元素作为单独的一个数组独立出来，对剩下的元素，逐个与前面的数组从后往前进行比较，一旦发现当前的元素大于或是等于前面已经排序好的元素中某个元素，则在这个元素之后插入即可；（3）在起泡法时，其算法思想是：将待排序的数组从后往前，依次比较相邻的两个元素，如果发现逆序则交换序列，使得数值、比较小的元素逐渐往前排列，在这个算法时要用flag作为标记位，用来判断元素是否交换，用以减少不必要的交换次数；（4）对于选择法，其排序思想是:从第一个元素开始，并且标记当前元素的位置，比较后面所有的元素，找到其中最小的元素，也标记当前元素的位置，然后把两个标记位的元素进行交换，前面的标记位不断地向后移动，直到最后一个元素的位置，则排序完成；（5）对于快速法，其算法思想是：一般取数组中的第一个元素为基准，通过一趟排序将待排序元素分为左右两个子序列，左子序列的所有元素都小于或等于右子序列的所有元素，然后将左右两个序列按照与此相同的原理进行排序，直至整个序列有序为止，排序完成。

实验4快速排序一、实验目的和要求1 在掌握各种排序方法的排序过程的基础上，完成快速排序算法程序设计。

2 能够对排序算法进行基本的复杂度分析。

二、实验内容排序就是把一组元素按照某个域的值的递增或递减的次序重新排列的过程。

快速排序在待排序记录序列中任取一个记录作为枢轴，以它作为比较的“基准”，将待排序划分为左右两个子序列，使行左边子序列中记录的关键字均小于等于枢轴，右边子序列中各记录的关键字都大于等于枢轴。

对所划分的两组分别重复上述过程，直到各个序列的记录个数为1时为止。

快速排序函数原型QuickSort(SeqList sq)。

设计一个算法，在顺序表存储结构上实现快速排序。

排序数据为学生的考试成绩单。

成绩单由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生的成绩单按照名次列打印出每个学生的名次、学号、姓名和成绩。

三、实验步骤1．输入待排序的记录2. 对自定义记录类型重载比较运算符3．排序1）并选择第一个记录作为pivotkey记录2）从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+13）.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-14）重复2),3)，直到low=high，将枢轴记录放在low(high)指向的位置5）重复2),3),4)，直到整个记录有序为止6) 输出排序记录，完成比较。

4. 附加要求：不采用运算法重载的方式，而是定义compare函数指针，通过传给quicksort 函数指针，完成排序。

四、实验提示算法实现：#include "iostream.h"#define MaxSize 100typedef int DataType;class CRecord{public:int No;string name;int grade;}Typdef CRecord DataType;class SeqList{public:CRecord * data;int length;}//创建顺序表V oid SLCreat(SeqList & sq);{ CRecord x;length = 0;cout <<"请输入数据元素数”;cin>>sq.length;sq.data= new CRecord[sq.length];cout <<"请输入数据元素值: no, , name grade ";for(int i = 0; i < n; i++){cin >> sq.data[i].no>>sq .data[i].name>>sq. data[i]grade;}}//排序V oid Sort( SeqList & sq ){ SLCreat(sq);QuickSort(sq,0,sq.length);}//快速排序void QuickSort(SeqList & sq, int low, int high){ int pos;if(low < high){ pos = partition(sq,low, high);QuickSort(sq,low, pos-1);QuickSort(sq, pos+1, high);}}int partition(SeqList & list, int i, int j){ DataType pivotkey;pivotkey = list[i];while(i < j){ while(i < j&&list[j] >= pivotkey) --j;if(i < j) list[i++] = list[j];while(i < j&&list[i] <= pivotkey) ++i;if(i < j) list[j--] = list[i];}list[i] = pivotkeylreturn i;}//将顺序表显示在屏幕上void SLPrint(SeqList & sq){cout <<"快速排序结果: "’for(int i = 0; i <list.length; i++)cout<<i<<sq.data[i].no<<sq .data[i].name<<sq. data[i].grade<<endl;cout << endl;}void main( ){ SeqList myList;SLCreat(SeqList &mylist);Sort(mylist );SLPrint( );}。

内排序算法的设计与实现
内部排序是指在排序过程中，待排序的所有数据都被放置在内存中，通过一系列的比较和交换操作将它们按照特定的顺序排列。

常见的内排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。

以下是一个使用 Python 实现冒泡排序算法的示例：
```python
def bubble_sort(arr):
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# 最后 i 个元素已经排好序
for j in range(0, n-i-1):
# 将当前最大的元素冒泡到末尾
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前的数组为:", arr)
bubble_sort(arr)
print("排序后的数组为:", arr)
```
冒泡排序算法的时间复杂度为$O(n^2)$，其中 n 是待排序数组的长度。

在最坏情况下，冒泡排序需要进行$n-1$轮比较和交换操作，每轮需要比较相邻的元素并进行交换。

因此，总的比较次数为$(n-1)\times n$，即$O(n^2)$。

虽然冒泡排序算法的时间复杂度较高，但它具有简单易懂、稳定性好等优点，适用于小型数组或对排序稳定性有要求的场景。

在实际应用中，通常会根据具体情况选择更高效的排序算法，如快速排序、归并排序等。

最新实验四排序实验报告实验目的：1. 理解并掌握四种基本排序算法：冒泡排序、选择排序、插入排序和快速排序的工作原理及其性能特点。

2. 通过编程实践，加深对算法效率和适用场景的理解。

3. 培养分析问题和解决问题的能力，提高编程技巧。

实验环境：- 操作系统：Windows 10- 编程语言：Python 3.8- 开发工具：PyCharm实验内容：1. 编写冒泡排序算法实现对一组随机整数的排序。

2. 实现选择排序算法，并对同样的一组随机整数进行排序。

3. 完成插入排序算法的编码，并用相同的数据集进行测试。

4. 编写快速排序算法，并比较其与其他三种排序算法的效率。

5. 分析比较不同排序算法在最坏、平均和最好情况下的时间复杂度。

实验步骤：1. 首先，生成一组包含50个随机整数的数据集。

2. 对于冒泡排序，重复交换相邻的元素，如果前者大于后者，则进行交换。

3. 对于选择排序，遍历数组，找到最小（或最大）的元素，将其与第一个元素交换，然后从剩下的元素中继续寻找最小（或最大）的元素，依此类推。

4. 插入排序的实现是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置。

5. 快速排序通过选定一个基准值，将数组分为两部分，一部分的元素都小于基准值，另一部分的元素都大于基准值，然后递归地在两部分上重复这个过程。

6. 使用计时器分别记录四种排序算法的执行时间，并进行比较分析。

实验结果：- 冒泡排序：平均时间复杂度为O(n^2)，在实验数据集上的执行时间为X秒。

- 选择排序：平均时间复杂度为O(n^2)，在实验数据集上的执行时间为Y秒。

- 插入排序：平均时间复杂度为O(n^2)，在实验数据集上的执行时间为Z秒。

- 快速排序：平均时间复杂度为O(n log n)，在实验数据集上的执行时间为W秒。

实验结论：通过实验，我们发现快速排序在大多数情况下都比其他三种简单排序算法有更高的效率。

冒泡排序、选择排序和插入排序在最坏情况下的时间复杂度都较高，适合处理小规模数据集或者基本有序的数据。

数据结构实验报告实验名称：实验4——用简单数组实现排序学生姓名：班级：班内序号：运行环境：VS20102010学号：日期：1．实验要求实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

1．实验要求使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性2. 程序分析2.1 存储结构数组：数组下标：0 1 2 3 4 5 62.2 关键算法分析(1)直接插入选择排基本思想：每次将一个待排序的记录按其关键码的大小插入到一个已经排序好的有序序列中，直到全部记录排序好。

设置r[0]为“哨兵”，从后向前查找有序区，边查找边后移，直到找到合适的位置，将r[0]插入。

每比较一次，k自增，每移动一次，m自增，最后输出m，k的值}void InsertSort(int r[], int n) //插入排序{int k=0;int m=0;int j;for (int i=2; i<=n; i++) //n-1趟排序{k++;if (r[i]<r[i-1]){r[0]=r[i];//将待插入记录赋值给哨兵r[0]r[i] = r[i-1];m++;for ( j = i-1; r[0]<r[j]; j--) //顺序查找{r[j+1] =r[j]; //元素后移k++;m++;}m++;数组元素r[j+1] = r[0];//插入记录}}cout<<endl<<"移动次数："<<m<<endl;cout<<"比较次数："<<k<<endl;}时间复杂度：O(n2)空间复杂度O(1)（2）希尔排序基本思想：将待排序的记录集分成多个子集，分别对这些子集进行排序，待整个序列基本有序时，在对记录进行一次直接插入排序。

四种排序算法比较1、概述：排序时计算机程序设计中的一种重要的操作。

它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

内部排序算法主要分为5大类，有十二个算法。

插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。

算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。

2、使用工具软件Microsoft Visual C++ 6.03实验内容3.1实验目的：掌握各种排序算法（直接插入排序、冒泡排序、快速排序、选择排序）的思路，并且比较它们之间的优缺点。

3.2程序设计：3.2.1主函数（sort.cpp）#include "stdafx.h"int main(int argc, _TCHAR* argv[]){int i;LARGE_INTEGER litmp;LONGLONG qt1,qt2;double dft,dff,dfm;QueryPerformanceFrequency(&litmp);//获得时钟频率dff=(double)litmp.QuadPart;int original[N];int arrayA[N];for(i=0;i<N;i++)// original[i]=i; //测试最好情况// original[i]=rand(); //测试一般情况original[i]=N-1-i; //测试最坏情况cout<<"初始化原始数据完成..."<<endl;cout<<"数据规模为:\t"<<N<<endl<<endl;for(i=0;i<N;i++)cout<<original[i]<<"\t";cout<<"\n";/////////////////////////////insertSort -插入排序for(i=0;i<N;i++)arrayA[i]=original[i];QueryPerformanceCounter(&litmp);//获得初始值qt1=litmp.QuadPart;insertSort(arrayA,N);QueryPerformanceCounter(&litmp);//获得终止值qt2=litmp.QuadPart;dfm=(double)(qt2-qt1);dft=dfm/dff;//获得对应的时间值，以秒为单位cout<<"插入排序耗时:\t"<<dft*1000<<"ms"<<endl<<endl;//////////////////////////selectSort -选择排序for(i=0;i<N;i++)arrayA[i]=original[i];QueryPerformanceCounter(&litmp);//获得初始值qt1=litmp.QuadPart;selectSort(arrayA,N);QueryPerformanceCounter(&litmp);//获得终止值qt2=litmp.QuadPart;dfm=(double)(qt2-qt1);dft=dfm/dff;//获得对应的时间值，以秒为单位cout<<"选择排序耗时:\t"<<dft*1000<<"ms"<<endl<<endl; ///////////////////////////bubbleSort -冒泡排序for(i=0;i<N;i++)arrayA[i]=original[i];QueryPerformanceCounter(&litmp);//获得初始值qt1=litmp.QuadPart;bubbleSort(arrayA,N);QueryPerformanceCounter(&litmp);//获得终止值qt2=litmp.QuadPart;dfm=(double)(qt2-qt1);dft=dfm/dff;//获得对应的时间值，以秒为单位cout<<"冒泡排序耗时:\t"<<dft*1000<<"ms"<<endl<<endl;/////////////////////////////quickSort -快速排序for(i=0;i<N;i++)arrayA[i]=original[i];QueryPerformanceCounter(&litmp);//获得初始值qt1=litmp.QuadPart;quickSort(arrayA,0,N-1);QueryPerformanceCounter(&litmp);//获得终止值 qt2=litmp.QuadPart;dfm=(double)(qt2-qt1);dft=dfm/dff;//获得对应的时间值，以秒为单位cout<<"快速排序耗时:\t"<<dft*1000<<"ms"<<endl<<endl; /////////////////////////////// duration=(double)(T2-T1)/CLOCKS_PER_SEC;// cout<<"快速排序耗时:\t"<<duration<<"s"<<endl<<endl;for(i=0;i<N;i++)cout<<arrayA[i]<<"\t";cout<<"\n\n";return 0;}3.2.2子函数（Func.cpp）1）插入法：一次将待排序的序列中的每一个记录插入到先前排序号的序列中，知道全部记录排序完毕。

第1篇一、实验背景排序算法是计算机科学中非常基础且重要的算法之一，它广泛应用于各种数据处理和科学计算领域。

为了更好地理解和掌握各种排序算法的原理、性能特点和应用场景，我们进行了排序性能分析实验。

本实验选取了九种经典的排序算法，包括插入排序、希尔排序、折半插入排序、冒泡排序、归并排序、快速排序、基数排序、堆排序和选择排序，通过实验对比分析这些算法的性能。

二、实验目的1. 掌握九种经典排序算法的原理和实现方法；2. 分析各种排序算法的时间复杂度和空间复杂度；3. 对比分析各种排序算法在不同数据规模和输入情况下的性能表现；4. 了解排序算法在实际应用中的适用场景。

三、实验方法1. 实验数据：随机生成大量不同规模的正整数序列，包括小规模、中等规模和大规模数据；2. 实验环境：使用C++语言进行编程实现，编译环境为Visual Studio 2019；3. 实验步骤：a. 编写九种排序算法的C++实现代码；b. 分别对每种算法进行测试，记录其执行时间和关键操作次数（如比较次数、移动次数）；c. 对比分析不同算法在不同数据规模和输入情况下的性能表现；d. 分析实验结果，撰写实验报告。

四、实验结果与分析1. 插入排序插入排序是一种简单直观的排序算法，基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

实验结果显示，插入排序在小规模数据上表现较好，但随着数据规模的增大，其性能明显下降。

2. 希尔排序希尔排序是插入排序的一种改进版本，通过将数据分为多个子序列，分别进行插入排序，从而提高排序效率。

实验结果表明，希尔排序在小规模数据上性能略优于插入排序，但在大规模数据上，其性能提升更为明显。

3. 折半插入排序折半插入排序是插入排序的一个变种，通过二分查找减少比较次数。

实验结果显示，折半插入排序在小规模数据上性能与插入排序相当，但在大规模数据上，其性能提升较为明显。

4. 冒泡排序冒泡排序是一种简单的排序算法，基本思想是通过重复地走访过要排序的数列，一次比较两个元素，若顺序错误则交换。

XXXXXX大学《数据结构》课程设计报告目录排序算法比较一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结排序算法比较一、需求分析利用随机函数产生N个随机整数（N = 500, 1000, 1500, 2000,2500, …,30000）, 利用直接插入排序、折半插入排序, 起泡排序、快速排序、选择排序、堆排序, 基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序）, 并统计每一种排序所耗费的时间（统计为图表坐标形式）。

二、程序的主要功能1.用户输入任意个数, 产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据, 并给出排序所用的时间。

三、程序运行平台Visual C++ 6.0版本四、数据结构本程序的数据结构为线形表, 线性顺序表、线性链表。

1.结构体:typedef struct{int *r; //r指向线形表的第一个结点。

r[0]闲置, 不同的算法有不同的用处, 如用作哨兵等。

int length; //顺序表的总长度}Sqlist;2.空线性表Status InitSqlist(Sqlist &L){L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间if(!L.r){printf("存储分配失败！");exit(0);} //存储分配失败L.length=0;//初始长度为0return OK;}五、算法及时间复杂度（一）各个排序是算法思想:（1）直接插入排序: 将一个记录插入到已排好的有序表中, 从而得到一个新的, 记录数增加1的有序表。

（2）折半插入排序: 插入排序的基本插入是在一个有序表中进行查找和插入, 这个查找可利用折半查找来实现, 即为折半插入排序。

数据结构--内部排序的比较存储管理、查找和排序班级：姓名：学号：完成日期：题目：内部排序算法比较问题描述：通过随机数据比较各算法的关键字比较次数与移动次数。

一、需求分析：内部排序方法有：插入排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。

二、概要设计本实验中用到的函数：1.起泡排序函数voidgenort(intb[],intn)2.插入排序函数voidinertort(qlitb,intn)3.希尔排序voidhellort(qlitb,intn)4.选择排序voidgentort(intb[],intn)5.快速排序voidquickort(qlitr,int,intt)6.堆排序voidift(qlitr,int,intm)三、详细设计#include#include#include#defineN66//头文件和宏定义intp,q;//全局变量//-----------------------起泡排序voidgenort(intb[],intn){ inti,j;int=0,t=0;for(i=0;ifor(j=i+1;jif(b[i]>b[j]){inttemp=b[i];b[i]=b[j];b[j]=temp;+=3;}}}cout<//-------------------------------插入排序typedefintKeyType; tructrec{KeyTypekey;};typedefrecqlit[N];voidinertort(qlitb,intn){inti,j;int=0,t=0;for(i=2;ib[0]=b[i];++;j=i-1;t++;while(b[0].keyb[j+1]=b[j];j--;++;t++;}b[j+1]=b[0];++;}cout<//------------------------------------希尔排序voidhellort(qlitb,intn){inti,j,gap;rec某;int=0,t=0;gap=n/2;while(gap>0){for(i=gap+1;ij=i-gap;while(j>0){t++;if(b[j].key>b[j+gap].key){某=b[j];b[j]=b[j+gap];b[j+gap]=某;j=j-gap;+=3;}elej=0;gap=gap/2;}}cout<//---------------------------------------选择排序voidgentort(intb[],intn){inti,j,k;int=0,t=0;for(i=0;ifor(j=i+1;jif(b[k]>b[j]){k=j;}}if(k!=i){inttemp=b[k];b[k]=b[i];b[i]=tem p;+=3;}}cout<//--------------------------------快速排序voidoutput(qlitb,intn)//输出元素值{for(inti=0;icout<voiddiplay(intn,intm)//输出计数{cout<voidBeforeSort()//初始化计数器{p=0;q=0;}voidquickort(qlitr,int,intt){inti=,j=t;if({r[0]=r[];p++;while(iwhile(i=r[0].key)j--;r[i]=r[j];q++;p++;p++;while(ir[j]=r[i];q++;p++;}r[i]=r[0];p++;}elereturn;quickort(r,,j-1);quickort(r,j+1,t);} voidort(qlitr,int,intt){BeforeSort();quickort(r,,t);diplay(p,q);}//---------------------------------堆排序voidift(qlitr,int,intm){intj;rec某;某=r[];for(j=2某;j<=m;j某=2){q++;if(jif(!(某.keyvoidheaport(qlit&r,intm){inti;recw;for(i=m/2;i>0;--i)ift(r,i,m);for(i=m;i>1;--i){ w=r[i];r[i]=r[1];r[1]=w;p+=3;ift(r,1,i-1);}}voidorting(qlit&r,intt){BeforeSort();heaport(r,t);diplay(p,q);}//-----------------------------------主函数voidmain(){ inta1[N],i;inte=N;for(i=0;icout<cout<cout<for(i=0;ia[i].key=e--;}inertort(a,N);e=N;for(i=0;ib[i].key=e--;}cout<cout<cout<intlow=0,high=10;for(i=0;i c[i].key=e--;}ort(c,low,high);cout<for(i=0;icout<cout<for(i=0;i{a1[i]=e++;}cout<cout<cout<for(i=0;ifor(i=0;ib[i].key=e++;}cout<cout<for(i=0;icout<e=1;for(i=0;icout<for(i=0;icout<cout<for(i=0;ia1[i]=rand()0;c1[i]=a1[i];a[i].key=a1[i];b[i].key=a1[i];c[i] .key=a1[i];d[i].key=a1[i];}cout<cout<genort(a1,izeof(a1)/izeof(int));cout<cout<cout<cout<cout<cout<cout<四、调试分析：程序运行基本正常。