# AlgorithmicJob
**Repository Path**: qinghongzhang/algorithmic-job
## Basic Information
- **Project Name**: AlgorithmicJob
- **Description**: 程序设计与算法作业
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-11-10
- **Last Updated**: 2023-11-27
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# 程序设计与算法作业
### 作业介绍
【排序算法：选择排序，归并排序，快速排序，希尔排序，基数排序】，对所有算法进
行分析并实现，分析其在不同规模的输入下单机性能变化情况；同时实现对于以下两种输入
的排序:
1. 对数值的范围在[`−10^100`, `10^100`]的数组排序，此项任务只能使用 C 或 C++完成。
2. 利用多线程实现大规模数据的分布式排序，输入超过 100 万为最低大规模要求。
### 软件架构
- bin: 可执行文件
- src: 源码
- include: 头文件
- build: 编译生成的中间文件
### 安装教程
1. 进入build目录，执行`cmake ..`
2. 生成makefile后，执行`make`,make后会在bin目录下生成可执行文件main
### 使用说明
1. 切换进bin后，执行`./main`
### 仓库地址
`https://gitee.com/qinghongzhang/algorithmic-job.git`
### 算法分析：
#### 1、选择排序
选择排序是一种简单直观的排序算法，它在实现上简单，对于刚开始有序的情况下，时间复杂度为O(n)，但对于大规模数据的排序效率较低。其时间复杂度为 O(n2)。在不同规模的输入下，选择排序的性能变化情况如下所示：
- 小规模数据：
当输入数据规模较小时，选择排序可能表现良好，实现简单，对于几百个甚至几千个元素的排序可能是合理选择。
由于其简单的实现方式，对于少量数据，选择排序的额外空间开销很小。
- 中等规模数据：
随着输入规模的增加，选择排序的性能迅速下降。对于数千到数万个元素的排序，选择排序的效率将明显变差，排序所需的时间将急剧增加。 它的时间复杂度 O(n2) 意味着随着输入规模的增加，排序时间会呈二次方级别增长，因此在中等规模数据上性能急剧下降。
- 大规模数据：
对于大规模数据集，选择排序的性能极其低下，排序所需的时间将会非常长，甚至难以接受。由于选择排序的时间复杂度 O(n2) 特性，其在大规模数据上的性能表现非常不理想，可能会变得非常慢。
总的来说，选择排序在性能上对于大规模数据是不具备优势的。随着输入规模的增加，其排序时间呈二次方级别增长，因此对于大规模数据的排序不是最佳选择。对于中小规模的数据集，选择排序可能是一个可行的选择。
#### 2、归并排序：
归并排序是一种高效的排序算法，它采用分治策略，将数组分成两个子数组，分别排序后再合并。其时间复杂度为 O(nlogn)。
在不同规模的输入下，归并排序的性能变化情况如下：
- 小规模数据：
对于小规模数据，归并排序的性能仍然相对较好。虽然它的时间复杂度为 O*(*n*log*n)，但由于递归和合并的开销，对于十几个甚至几百个元素的排序，可能比一些简单的排序算法稍慢。
- 中等规模数据：
随着输入规模的增加，归并排序的性能保持较为稳定且高效。对于数千到数十万个元素的排序，归并排序通常表现良好，其时间复杂度 O(nlogn) 保证了排序时间不会随着输入规模的增加呈指数级增长。归并排序的稳定性和可靠性使其在中等规模数据上能够提供高效的排序。
- 大规模数据：
归并排序在大规模数据集上依然保持着较好的性能表现。虽然对于数百万甚至更大规模的数据集排序可能耗时较长，但其时间复杂度 O(nlogn) 保证了排序时间不会随着输入规模的增加呈指数级增长。对于大规模数据集，归并排序通常是一个较好的选择，特别是当你需要考虑稳定性时。
总的来说，归并排序在不同规模的数据输入下都能保持较好的性能。它的稳定性和时间复杂度 O(nlogn) 特性使其适用于大多数场景。尽管在小规模数据上可能不如一些简单排序算法快速，但在中等和大规模数据集上，归并排序通常是一个高效可靠的排序算法。
#### 3、快速排序：
快速排序是一种高效的排序算法，它利用分治策略和递归思想，通过选择一个基准值，将数组分成两个子数组，然后对子数组进行排序。其时间复杂度为平均情况下 O(nlogn)，但最坏情况下可能达到O(n2)。
在不同规模的输入下，快速排序的性能变化情况如下：
- 小规模数据：
对于小规模数据，快速排序通常表现良好。虽然它的平均时间复杂度为 O(nlogn)，但是在刚开始有序或者逆序的时候会退化为 O(n2)。
- 中等规模数据：
快速排序在中等规模数据上通常表现出色。对于数千到数十万个元素的排序，快速排序的平均时间复杂度 O(nlogn) 使得其在大多数情况下能够快速、高效地完成排序。
尽管最坏情况下时间复杂度为 O(n2)，但在实际应用中，快速排序的平均情况更为常见，因此其在中等规模数据上仍然是一个优秀的选择。
- 大规模数据：
在大规模数据集上，快速排序通常表现良好。尽管在最坏情况下可能出现 O(n2) 的时间复杂度，但其平均时间复杂度 O(nlogn) 保证了对大规模数据的高效排序，所以快速排序在大规模数据排序时通常能够提供较好的性能表现。
总的来说，快速排序在不同规模的数据输入下通常表现出色。尽管在最坏情况下可能出现O(n2) 的时间复杂度，但在实际应用中，平均情况下的 O(nlogn) 时间复杂度使得快速排序成为一个高效、广泛应用的排序算法。在处理大规模数据时，快速排序通常能够提供较好的性能，但需要注意最坏情况下的时间复杂度。
#### 4、希尔排序：
希尔排序是插入排序的一种改进，它通过比较距离较远的元素进行交换，从而使得数组中的元素迅速朝最终位置前进。其核心思想是将数组分成若干个子序列，对子序列进行插入排序，最终完成排序。
希尔排序的性能在不同规模的输入下表现如下：
- 小规模数据：
对于小规模数据，希尔排序通常能够表现良好。由于它的改进算法特性，对于少量元素的排序，希尔排序可能比一些简单的排序算法更高效。虽然其平均时间复杂度为 O(n1.3) 到 O(n2) 之间，但对于小规模数据集，希尔排序通常仍能提供较好的性能。
- 中等规模数据：
在中等规模数据下，希尔排序通常仍然是一个较为高效的排序算法。对于数千到数十万个元素的排序，希尔排序的性能相对较好。
希尔排序通过改进插入排序，其时间复杂度相对于普通的插入排序在中等规模数据上有所提升，因此通常在这个规模下表现良好。
- 大规模数据：
在大规模数据集上，希尔排序的性能可能略显不足。尽管在平均情况下时间复杂度较优，但对于大规模数据，其性能可能不及归并排序、快速排序等 O(nlogn) 级别的排序算法。希尔排序在大规模数据上的性能可能受选取的间隔序列的影响较大，不同的间隔序列可能会导致性能差异。
总的来说，希尔排序在小到中等规模的数据上表现良好，但对于大规模数据，其性能可能不及 O(nlogn) 级别的排序算法。选取合适的间隔序列对希尔排序的性能影响较大，在实际使用中需要考虑到数据规模和性能的平衡。
#### 5、基数排序：
基数排序是一种非比较性的整数排序算法，它按照数字的位数进行排序，将数字按位数分配到桶中，然后依次收集，最终完成排序。其时间复杂度为 O(kn)，其中 k 是数字的位数。
基数排序在不同规模的输入下性能表现如下：
- 小规模数据：
对于小规模数据，基数排序通常能够表现良好。虽然其时间复杂度是线性的 O(kn)，但在位数较少的情况下，排序通常会比较快速。
- 中等规模数据：
在中等规模数据下，基数排序的性能通常也较好。当数据规模适中且位数不是很大时，基数排序可以提供较好的排序效率，常常表现稳定。
- 大规模数据：
基数排序在大规模数据上的性能取决于数字的位数。如果数字的位数较少，即使数据规模很大，基数排序也可能表现良好。但如果数字的位数很大，即使在大规模数据下，基数排序的性能也可能受到影响。此时，时间复杂度中的 k 可能会成为影响性能的因素，排序所需时间可能会相对较长。
总体来说，基数排序的性能在很大程度上取决于数字的位数和数据规模。对于位数较少且数据规模适中的情况，基数排序通常能够提供较好的性能表现。但在位数较多且数据规模很大时，基数排序的性能可能会受到影响，需要考虑其线性时间复杂度 O(kn) 的影响。在实际应用中，需要根据具体情况选择合适的排序算法以获得更好的性能。
#### 6、 大规模数据分布式排序
大规模数据的分布式排序：
- 数据量不够大时，多线程排序不占优势，因为传统算法本身就很快，可以在秒时间内完成，而线程的创建、销毁开销比本身排序开销还大。
- 随着数据量规模的提升，多线程并行排序效率更好，但是算上线程创建、销毁等开销还是和传统排序差不多。
- 当数据量达到一定规模后，多线程并行排序明显要好于传统排序，性能会提升好几倍。
### 测试
- 测试不同排序方法在不同规模的输入下单机性能的变化
| 排序方法 |
数据规模 |
耗费时间 |
| 选择排序 |
100 |
69us506ns |
| 1000 |
3ms374us104ns |
| 10000 |
307ms770us59ns |
| 100000 |
35s605ms142us44ns |
| 1000000 |
超时 |
| 5000000 |
超时 |
| 10000000 |
超时 |
| 基数排序 |
100 |
53us769ns |
| 1000 |
499us699ns |
| 10000 |
5ms705us503ns |
| 100000 |
42ms362us140ns |
| 1000000 |
400ms38us611ns |
| 5000000 |
1s996ms877us250ns |
| 10000000 |
3s991ms143us946ns |
| 归并排序 |
100 |
41us944ns |
| 1000 |
595us384ns |
| 10000 |
13ms682us720ns |
| 100000 |
90ms341us265ns |
| 1000000 |
1s12ms267us230ns |
| 5000000 |
5s773ms724us351ns |
| 10000000 |
11s295ms767us781ns |
| 快速排序 |
100 |
17us663ns |
| 1000 |
271us94ns |
| 10000 |
4ms173us960ns |
| 100000 |
46ms465us976ns |
| 1000000 |
553ms837us293ns |
| 5000000 |
3s236ms462us315ns |
| 10000000 |
6s501ms272us101ns |
| 希尔排序 |
100 |
31us906ns |
| 1000 |
386us285ns |
| 10000 |
7ms546us489ns |
| 100000 |
98ms992us587ns |
| 1000000 |
1s206ms326us625ns |
| 5000000 |
7s534ms494us384ns |
| 10000000 |
15s609ms442us787ns |
- 大规模数据分布式排序性能分析
| 数据规模 |
线程数 |
传统快速排序 |
分布式快速排序 |
| 1000000 |
2 |
495ms333us |
1s197ms919us |
| 4 |
1s368ms875us |
| 8 |
1s339ms75us |
| 16 |
1s330ms685us |
| 5000000 |
2 |
2s630ms724us |
1s900ms472us |
| 4 |
2s936ms837us |
| 8 |
2s845ms375us |
| 16 |
2s848ms937us |
| 10000000 |
2 |
11s182ms759us |
3s433ms68us |
| 4 |
4s641ms298us |
| 8 |
4s699ms272us |
| 16 |
4s962ms153us |