c++数据结构算法复习基础--12--排序算法-常见笔试面试问题

embedded/2024/12/19 20:42:15/

1、STL里sort算法用的是什么算法>排序算法?

快速算法>排序算法
插入排序(待排序序列个数<32时,系统默认32)。
递归层数太深,转成堆排序。

#include<algorithm> //算法库,头文件

使用了快速排序:

sort原码:
在这里插入图片描述
小到大

_EXPORT_STD template <class _RanIt>
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last) { // order [_First, _Last)_STD sort(_First, _Last, less<>{});

在这里插入图片描述

EXPORT_STD template <class _RanIt, class _Pr>
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last)_STD _Adl_verify_range(_First, _Last);const auto _UFirst = _STD _Get_unwrapped(_First);const auto _ULast  = _STD _Get_unwrapped(_Last);_STD _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _STD _Pass_fn(_Pred));
}

使用了插入排序

在这里插入图片描述

快速排序的优化

上图可知,当区间元素个数小于等于_ISORT_MAX 时(默认是32,如下图所示),直接转成插入排序
当数据趋于有序,插入排序是效率最高的。

if (_Last - _First <= _ISORT_MAX) { // small_STD _Insertion_sort_unchecked(_First, _Last, _Pred);return;
}

在这里插入图片描述

使用了堆排序

在这里插入图片描述
在这里插入图片描述

2、快速排序的时间复杂度不是稳定的nlogn,最坏情况会变成n^2,怎么解决复杂度恶化问题?

1)随着快排的进行,当所需排列的队列足够小,进行快速排序。
2)找取合适的基准数,三数取中,使其逻辑上的二叉树更加平衡。

3、快速排序递归实现时,怎么解决递归层次过深的问题?

下面引用的是c++STLsort原码
多加一个参数,系统为_Ideal,初始的时候是元素的个数,
在这里插入图片描述

template <class _RanIt, class _Pr>
_CONSTEXPR20 void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t<_RanIt> _Ideal, _Pr _Pred) {// order [_First, _Last)

每进行一次,对_Ideal进行缩减

_Ideal = (_Ideal >> 1) + (_Ideal >> 2); // allow 1.5 log2(N) divisions

当递归到某一个层次的时候,发现_Ideal <= 0;,就可知道我们想控制的递归快排深度就已经到达了。对剩下的元素,进行想用的排序。系统原码使用的是堆排序。

 if (_Ideal <= 0) { // heap sort if too many divisions_STD _Make_heap_unchecked(_First, _Last, _Pred);_STD _Sort_heap_unchecked(_First, _Last, _Pred);return;}

4、递归过深会引发什么问题?

引发效率过慢,函数调用次数过多,函数开销过大
栈相对于堆很小,容易导致栈内存溢出,程序挂掉

调用一个函数需要“压”很多东西,函数执行完,又要从栈内“弹出”很多东西。一个函数的调用,包含“压”参数、压ebp、压下一行指令地址、栈帧开辟、栈帧回退、处理返回值、弹出下一行指令地址、弹出ebp等等。

5、怎么控制递归深度?如果达到递归深度了还没排完序怎么办?

如题目三,没排完,转另一个非递归的算法>排序算法

6、

【2015阿里巴巴研发工程师笔试题】个数约为50K的数列需要进行从小到大排序,数列特征是基本逆序(多数数字从大到小,个别乱序),以下哪种算法>排序算法在事先不了解数列特征的情况下性能最优。( )
A.冒泡排序
B.改进冒泡排序
C.选择排序
D.快速排序 ---- 越乱越好
E.堆排序
F.插入排序 ----- 趋于有序,这里的基本逆序,趋于n*n

7、

【2016阿里巴巴校招笔试题】现有1GB数据进行排序,计算资源只有1GB内存可用,下列排序方法中最可能出现性能问题的是()
A.堆排序
B.插入排序
C.归并排序 — 空间复杂度最大
D.快速排序
E.选择排序
F.冒泡排序

8、

【京东】假设你只有100Mb的内存,需要对1Gb的数据进行排序,最合适的算法是()
A.归并排序
B.插入排序
C.快速排序
D.冒泡排序

对于改题目具体实现:

数据量:1G == 1024M
内存:100M
数据无法一次加载到内存上,大概十一倍的。
假如数据存放于src.txt上。

1、创建11个文件,如src01.txt ,src02.txt … src11.txt
2、循环读取原始文件src.txt,每读出一个数据,轮询放入上面的十一个小文件当中。
(此时,每一个小文件存储的数据大小,不足100M)
3、分别把每一个小文件的数据,全部加载到内存上,进行排序,完成后,把排序的结果写回到相应的小文件当中。
(此时所以小文件里面的数据是有序的)
4、利用归并思想,分别循环依次读入src01.txt 和 src02.txt 的一个数据,选出小值,写入最终的src012.txt 文件中。被写入的数据,从其对应的文件读入下一个数据,循环处理,直到两个文件的数据合并完成。
(将两个小段有序的文件,合并成一个大段有序的文件)
5、src03 <=> src04 等等,依次处理直到最后一个文件

9、内排序和外排序

内排序 – 数据都在内存上。
外排序 – 内存小,数据量大, 无法一次性将数据都加载到内存上。
前面讲的排序,只有归并是外排序,其余都是内排序。

各种算法>排序算法代码

#include<iostream>
#include<stdlib.h> //包含随机数函数srand
#include<time.h> //需要用time作为随机数种子
#include<string>
#include<stack>
#include <functional>using namespace std;//冒泡算法>排序算法
void BubbleSort(int arr[], int size)
{for (int i = 0; i < size; i++)//趟数{//一趟的处理//进行优化,如果某趟没有进行如何的数据交换,那么说明数据已经有序bool flag = false;for (int j = 0; j < size - 1 - i; j++){if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = true;}}if( !flag )//if (flag = false){//如果没有做任何的数据交换,那么说明数据已经有序了return;}}
}//选择算法>排序算法
void ChoiceSort

http://www.ppmy.cn/embedded/147103.html

相关文章

《Python制作动态爱心粒子特效》

一、实现思路 粒子效果&#xff1a; – 使用Pygame模拟粒子运动&#xff0c;粒子会以爱心的轨迹分布并运动。爱心公式&#xff1a; 爱心的数学公式&#xff1a; x16sin 3 (t),y13cos(t)−5cos(2t)−2cos(3t)−cos(4t) 参数 t t 的范围决定爱心形状。 动态效果&#xff1a; 粒子…

智能文档处理百宝箱,文档处理的必备利器

1、引言 文档解析是开发者在业务实践中会频繁面临的场景&#xff0c;不管是用AI辅助日常工作&#xff0c;还是从事产品研发&#xff0c;从非结构化文本中提取文字、图片等信息具有很大的挑战。 目前市面上的文档解析工具普遍存在繁杂无序&#xff0c;缺乏统一评估标准&#xff…

【机器学习】解构概率,重构世界:贝叶斯定理与智能世界的暗语

文章目录 条件概率与贝叶斯定理&#xff1a;深入理解机器学习中的概率关系前言一、条件概率与贝叶斯定理1.1 条件概率的定义与公式1.1.1 条件概率的定义1.1.2 条件概率的实例讲解 1.2 条件概率的性质与法则1.2.1 链式法则1.2.2 全概率公式1.2.3 贝叶斯定理的推导 1.3 贝叶斯定理…

【Leetcode 每日一题 - 扩展】1326. 灌溉花园的最少水龙头数目

问题背景 在 x x x 轴上有一个一维的花园。花园长度为 n n n&#xff0c;从点 0 0 0 开始&#xff0c;到点 n n n 结束。 花园里总共有 n 1 n 1 n1 个水龙头&#xff0c;分别位于 [ 0 , 1 , . . . , n ] [0, 1, ..., n] [0,1,...,n]。 给你一个整数 n n n 和一个长度…

练习题:一维数组

练习题 第一题 键盘录入一组数列&#xff0c;利用冒泡排序将数据由大到小排序 代码 #include <stdio.h>int arr_home01() {int arr[10];int i,j,temp;printf("请输入10个测试整数&#xff1a;\n");int len sizeof(arr) / sizeof(arr[0]);for(i 0;i < …

SpringMVC的使用

之前我们介绍了如何创建SpringMVC工程&#xff0c;本期介绍如何如何更加详细的使用SpringMVC。 这里给出之前的链接&#xff1a;如何创建SpringMVC工程-CSDN博客 1.跳转不经过视图解析器 之前我们为SpringMVC工程添加了视图解析器&#xff0c;使得每个返回的字符串请求都会加…

如何使用arping命令检测IP地址冲突?

不同的操作系统对于IP地址冲突都有着不同的检测与解决方法。 在Windows系统之中&#xff0c;如果出现IP地址冲突&#xff0c;系统会显示图表进行提示&#xff0c;你可以根据图标来进行后续的操作&#xff0c;尽可能的避免IP地址冲突带来的影响。 而在Linux系统之中是没有类似的…

游戏引擎学习第49天

仓库: https://gitee.com/mrxiao_com/2d_game 回顾 我们当时在讨论我们必须要进行一些改进&#xff0c;以便在游戏中实现更好的碰撞检测。当时展示了一种非常基本的形式&#xff0c;以十字路口为例来实现碰撞交叉工作。然后我们意识到需要升级到更复杂的水平&#xff0c;以便…