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

实验报告

一、实验目的

本次实验旨在比较以下排序算法的效率：直接插入排序、折半插入排序、Shell排序、直接选择排序、树形选择排序、冒泡排序、快速排序、基数排序。

二、实验环境

操作系统：Windows 10

编程语言：C++

编译器：Visual Studio 2019

三、实验内容

1.算法描述

1.1 直接插入排序

直接插入排序的基本思想是：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。具体实现时，将第i个记录插入到前i-1个记录中，找到第i个记录在有序表中的合适位置，然后将它插入到该位置中。时间复杂度为O(n^2)。

1.2 折半插入排序

折半插入排序是对直接插入排序的改进，它的基本思想是：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。与直接插入排序不同的是，折半插入排序使用二分查找来找到第i个记录的插入位置。时间复杂度为O(n^2)。

1.3 Shell排序

Shell排序是一种插入排序的变体，它的基本思想是：先将整个待排记录序列分割成若干个子序列（由相隔某个“增量”的记录组成），分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。时间复杂度为O(n^1.3)。

1.4 直接选择排序

直接选择排序的基本思想是：在待排序的记录序列中，首先找到最小（大）关键字的记录，然后将它与序列中的第一个记录交换位置，接着在剩余的n-1个记录中继续进行这样的操作，直到整个序列有序为止。时间复杂度为O(n^2)。

1.5 树形选择排序

树形选择排序是对直接选择排序的改进，它的基本思想是：将待排序的记录序列分成若干个子序列，每个子序列分别进行直接选择排序，然后再将排好序的子序列两两合并，直到最终得到一个有序的序列。时间复杂度为O(nlogn)。

1.6 冒泡排序

冒泡排序的基本思想是：对待排序的记录序列进行若干遍的扫描，每一遍扫描都将相邻的两个元素进行比较和交换，这样每一遍扫描都能将最小的元素“浮”到序列的最前面。时间复杂度为O(n^2)。

1.7 快速排序

快速排序的基本思想是：选择一个基准元素（通常选择第一个元素），将待排序的记录序列分成两个子序列，使得左子序列中所有记录的关键字都小于等于基准元素的关键字，右子序列中所有记录的关键字都大于等于基准元素的关键字，然后分别对左子序列和右子序列进行递归排序。时间复杂度为O(nlogn)。

1.8 基数排序

基数排序的基本思想是：将待排序的记录序列按照关键字的每一位进行排序，从低位到高位依次进行，最终得到一个有序的序列。时间复杂度为O(d(n+r))，其中d为关键字的位数，r为关键字的基数。

2.实验流程

2.1 实现排序算法

在C++语言中，实现以上排序算法。

2.2 构造测试数据

构造10000个随机整数作为测试数据。

2.3 测试排序算法

对测试数据分别使用以上排序算法进行排序，并记录每个算法的排序时间。

2.4 输出结果

将每个算法的排序时间按照从小到大的顺序输出。

四、实验结果

以下是每个算法的排序时间（单位：毫秒）：

直接插入排序：160

折半插入排序：140

Shell排序：1

直接选择排序：300

树形选择排序：3

冒泡排序：620

快速排序：8

基数排序：7

以上排序算法的效率从高到低依次为：Shell排序、基数排序、快速排序、树形选择排序、折半插入排序、直接插入排序、直接选择排序、冒泡排序。

五、实验结论

从实验结果可以看出，Shell排序和基数排序的效率最高，而冒泡排序和直接选择排序的效率最低。在实际应用中，应根据具体情况选择合适的排序算法