- 1【深度学习】GPT-2，Language Models are Unsupervised Multitask Learners，【语言建模】
- 2【万字长文】向 AI 提问的艺术_ai提问的艺术
- 3Python球球大作战（完整代码）_以下代码将显示'yes + no':mystr = 'yes'yourstr = 'no'mystr
- 4博科光纤交换机300
- 5优雅地断开TCP连接_tcp长链接 优雅关闭
- 6ubuntu下Anaconda环境安装GPU的pytorch(docker镜像)_pytorch ubuntu
- 7mysql数据库包含什么_Mysql数据库中有哪些数据类型?
- 8重磅！ChatGPT 网页版来啦！响应速度超快！_chtegtp网页版
- 9全面解读：ChatGPT与大模型技术家族——GPT、AIGC、LLM解析_chatgpt和llm大模型
- 10def __init__(self)是什么意思_通俗的告诉你Python中 init_ 到底是什么含义？_def init self什么意思
八种基本排序的含图详解_需要从一个文件里面读取一百万个32位整数,排序后输出到文件,程序运行在64位pc上。
赞
踩
排序的概念
排序:
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的。
内部排序: 数据元素全部放在内存中的排序。
外部排序: 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
八种基本排序的对比：
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
| 基数排序 | O(d(r+n)) | O(d(n+rd)) | O(d(r+n)) | O(n+rd) | 稳定 |
注：基数排序的复杂度中，r代表关键字的基数，d代表位的长度，n代表关键字的个数
在基数排序中排列数组各位的运行时间为O(n+r)
各种排序的适用场景：
- 大多数情况 （包含大量的重复元素） ------ 快速排序
- 大部分数据离他正确的位置很近，近乎有序的 ------ 插入排序
- 数据的取值范围有限，如：学生成绩排序 ------ 计数排序
- 稳定的排序（数据使用链表存储）------ 归并排序
- 数据量超级大，或内存太小 ------ 使用外排序
当输入规模n比较小的时候，应该使用选择排序或者插入排序（插入排序通常会比选择排序少一些比较的次数，但是选择排序会比插入排序少挪动的次数）；
详解八种排序的入口：
知识点习题
- 假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是？
A. 归并排序
B. 插入排序
C. 快速排序
D. 冒泡排序
正确答案
A
答案解析
内存装不下，所以只能从外部排序中选择，根据题设，可以得出用归并排序比较好
- 先将1G分为10个100M(这里1G可理解近似等于1000M，方便讲解思路)，分别加载10个100M数据到内存中，分别对其进行排序；
- 然后10文件每个文件选取10M加载到内存进行排序，依次进行。
即先分解再归并的思路。
- 下列各排序法中，最坏情况下的时间复杂度最低的是( )
A. 希尔排序
B. 快速排序
C. 堆排序
D. 冒泡排序
正确答案: C
参考答案:
堆排序最坏情况时间下的时间复杂度为 O(nlog2n) ;希尔排序最坏情况时间下的时间复杂度为 O(n1.5) ;快速排序、冒泡排序最坏情况时间下的时间复杂度为 O(n2) 。
- 以下排序方式中占用O(n)辅助存储空间的是
A. 简单排序
B. 快速排序
C. 堆排序
D. 归并排序
正确答案： D
答案解析：
归并排序在归并过程中需要与原始序列相等的存储空间O（n）用于存放归并结果：
递归实现的归并排序还需考虑深度为log2n的栈空间，因此空间复杂度为O（n+log2n）;
而非递归实现的归并排序避免了递归时深度为log2n的栈空间，因此空间复杂度为O（n）。
归并排序是所有排序中占用内存最多，但是效率比较高且稳定的算法，即牺牲内存提高了效率。
- 有一项考试的成绩，目前是按照完成时间进行升序排列的，需要按照考试成绩进行排序，成绩高的排在前面，如果成绩相同，则完成时间短的排在前面。以上场景适合采用下列哪些排序算法？
A.插入排序 B.快速排序 C.堆排序 D.冒泡排序
正确答案： A，D
答案解析：
本题实际考察哪种排序算法是稳定的，插入、冒泡是稳定的，快速和堆是不稳定的。
- 需要从一个文件里面读取一百万个32位整数，排序后输出到文件，程序运行在64位PC上。
整数数值范围在0到500之间。程序的内存限制是2K，要求1秒内出结果。请选择一种高效可行的排序算法。
A. 希尔排序法
B. 冒泡排序法
C. 计数排序
D. 快速排序
正确答案： C
答案解析：
计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。
它适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(nlogn)的排序，例如快速排序、归并排序。
不论是难还是简单，自己上手多写几遍，都是可以掌握的排序算法。一起加油！！！
