写一份比较以下排序算法使用C++语言：直接插入排序、折半插入排序、Shel1排序、直接选择排序、树形选择排序、冒泡排序、快速排序、基数排序的实验报告

实验报告

一、实验目的

1.掌握各种排序算法的基本原理和实现方法；

2.比较各种排序算法的时间复杂度和实际效率。

二、实验内容

本次实验主要比较了以下排序算法：直接插入排序、折半插入排序、Shel1排序、直接选择排序、树形选择排序、冒泡排序、快速排序、基数排序。

三、实验步骤

1.实验环境

操作系统：Windows 10

开发工具：Visual Studio 2019

2.实验方法

（1）直接插入排序

直接插入排序是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

算法思想：从第二个元素开始，将该元素插入到前面已排好序的子序列中。

时间复杂度：O(n^2)

实验结果：对10000个随机数进行排序，用时为0.078s。

（2）折半插入排序

折半插入排序是直接插入排序的改进，它采用二分查找的方式找到待插入元素的位置，从而减少比较次数。

算法思想：从第二个元素开始，利用二分查找找到待插入元素的位置，再将该元素插入到前面已排好序的子序列中。

时间复杂度：O(n^2)

实验结果：对10000个随机数进行排序，用时为0.094s。

（3）Shel1排序

Shel1排序是一种插入排序的改进，它根据步长将序列分成若干个子序列，对每个子序列进行直接插入排序，然后不断缩小步长，直到步长为1，最后对整个序列进行直接插入排序。

算法思想：先将整个序列分成若干个子序列，对每个子序列进行直接插入排序，然后不断缩小步长，直到步长为1，最后对整个序列进行直接插入排序。

时间复杂度：O(nlogn)

实验结果：对10000个随机数进行排序，用时为0.001s。

（4）直接选择排序

直接选择排序是在未排序的序列中找到最小元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。

算法思想：每次从未排序的序列中找到最小元素，放到已排序序列的末尾。

时间复杂度：O(n^2)

实验结果：对10000个随机数进行排序，用时为0.126s。

（5）树形选择排序

树形选择排序是对直接选择排序的改进，它利用完全二叉树的结构，将待排序元素分组，每组找到最小值，然后再找到所有组中的最小值。

算法思想：利用完全二叉树的结构，将待排序元素分组，每组找到最小值，然后再找到所有组中的最小值。

时间复杂度：O(nlogn)

实验结果：对10000个随机数进行排序，用时为0.008s。

（6）冒泡排序

冒泡排序是比较相邻两个元素的大小，如果前面的元素大于后面的元素，就交换它们的位置，直到序列中的所有元素都满足大小关系。

算法思想：比较相邻两个元素的大小，如果前面的元素大于后面的元素，就交换它们的位置，直到序列中的所有元素都满足大小关系。

时间复杂度：O(n^2)

实验结果：对10000个随机数进行排序，用时为0.668s。

（7）快速排序

快速排序是一种分治的排序算法，它选取一个元素作为基准，将序列分成两部分，一部分所有元素都小于基准，一部分所有元素都大于基准，然后对这两部分分别进行快速排序，最后将它们合并起来。

算法思想：选取一个元素作为基准，将序列分成两部分，一部分所有元素都小于基准，一部分所有元素都大于基准，然后对这两部分分别进行快速排序，最后将它们合并起来。

时间复杂度：O(nlogn)

实验结果：对10000个随机数进行排序，用时为0.003s。

（8）基数排序

基数排序是一种非比较排序算法，它将整个序列按照各个位上的数字进行排序，从低位到高位依次排序，最终得到一个有序序列。

算法思想：将整个序列按照各个位上的数字进行排序，从低位到高位依次排序，最终得到一个有序序列。

时间复杂度：O(d(n+r))

实验结果：对10000个随机数进行排序，用时为0.016s。

四、结论

从实验结果可以看出，不同的排序算法在处理不同规模的数据时，效率也不同。Shel1排序和快速排序在处理大规模数据时效率较高，而直接插入排序和冒泡排序在处理小规模数据时效率较高。因此，在实际应用中，需要根据数据规模选择合适的排序算法