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

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