588-排序算法常见问题

墨蓝 2022-08-28 13:56 6阅读 0赞

![在这里插入图片描述][16c4f81239a6461d81c8eb478d3b8749.png]  
**算法库的头文件**

## 问题1 ##

![在这里插入图片描述][75643e3d40c449af845f48f03371ff20.png]  
**sort源码：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**（堆排序）**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

\_Ideal是元素的个数  
**每次递归：\_Ideal都要缩小**  
\_Ideal来控制栈的深度，是为了让树趋于平衡的情况，如果超过这个，认为此时序列趋于有序，认为树的倾斜度高，而且如果元素过多，快排递归次数过多，会把栈撑破。此时每段序列比较短，适合堆排。  
**当递归达到 \_Ideal<=0，而且此时元素量也比较少了，序列就短了，就把快排转为堆排序，空间复杂度是O(1)**  
如果用归并，占用额外的内存空间会比较多。  
控制到1.5倍的log以2为底的n  
![在这里插入图片描述][f410054879c24e5d822cfb3244953302.png]  
**（快速排序算法+插入排序算法）**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][43682f54aaf64b81a5b856d6d96fbcd1.png]  
![在这里插入图片描述][df0446855ed842dfbdb4b849865d3487.png]

## 问题2 ##

![在这里插入图片描述][8ee18504279840bba432335fe4d15759.png]  
![在这里插入图片描述][9fd6d10f886149f281b6939c20819fc9.png]

## 问题3 ##

![在这里插入图片描述][e169ac4abef4445da988ba121cf026b7.png]  
在sort源码，通过参数\_Ideal(元素的个数)  
![在这里插入图片描述][523d3ab2e4524f9aa5e42e1bc8700c2a.png]  
**每次递归，对\_Ideal进行缩减，直到\_Ideal<=0的时候，转成堆排序**  
![在这里插入图片描述][b759e2cdfaf844e49c9810d9ec1ecb2d.png]

## 问题4 ##

![在这里插入图片描述][d8a4e8c8afe14cefb1cacef2841ad6f2.png]  
**效率变慢**  
递归是函数自己调用自己，调用一次函数，就有函数的开销（栈帧开辟，压很多东西，弹出很多东西，栈帧回退），如果递归过深，说明函数调用次数过多，函数开销变大，  
栈内存相对来说比较小，递归过深，说明函数调用次数过多，导致栈内存溢出，程序挂掉  
![在这里插入图片描述][52adef81a2214924b8d46c934b4e3c1c.png]

## 问题5 ##

![在这里插入图片描述][f27466d28d834ef69092f2df82823451.png]  
**参考问题3的答案**  
**没排完，转成另一个非递归的排序算法就可以了，一般用堆排序（平均，最坏，最好的时间复杂度都是一样的）**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

## 问题6 ##

![在这里插入图片描述][0193188f7de149a2b7d2e6eef5e2b5a8.png]  
**选择E：堆排序**  
在事先不了解数据特征，在最坏，最好，平均的时间复杂度都是O(nlogn)

## 问题7 ##

![在这里插入图片描述][1563836602374a74b0872aa9c6d99ebd.png]  
**只能原地排序，不能占用额外的内存空间，空间复杂度是O(1)**  
数据是1G，内存是1G  
**选择C归并排序**（空间复杂度最大，1次只能排序1部分，没有排序的在磁盘上，磁盘I/O操作多）  
![在这里插入图片描述][9be70acf4b2640e39fe97e8e8cd1f3bf.png]

## 问题8 ##

![在这里插入图片描述][1e189a64027943babd726c0787d37072.png]  
**选择A 归并排序**  
只有归并排序可以进行外排序（磁盘上的数据排序，其他排序算法都是内排序）  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]  
**归并排序在这个场景怎么排？**  
![在这里插入图片描述][01e861a397174068a86f9ed3140a0d2a.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
外排序涉及的是磁盘I/O，效率比较低。

[16c4f81239a6461d81c8eb478d3b8749.png]: /images/20220828/22d3c7cd2c1c470f8f593379b54314da.png
[75643e3d40c449af845f48f03371ff20.png]: /images/20220828/d59b4b643eb74ab2b2d191e8f28a5ba9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/38911d55d83c460fa6a44c9ffb43212a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ef9ba7de17154ce694522a88150f3e2b.png
[f410054879c24e5d822cfb3244953302.png]: /images/20220828/c086870bb72d4a148eca1f6154560c19.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/913d0bd7aa5b41f8a9e67d66bfaeab25.png
[43682f54aaf64b81a5b856d6d96fbcd1.png]: /images/20220828/dd97415644654ae498efc66824aa55b5.png
[df0446855ed842dfbdb4b849865d3487.png]: /images/20220828/56a71971f94547c49b0600769f8d65da.png
[8ee18504279840bba432335fe4d15759.png]: /images/20220828/e862bb37e1fb46e3843d8d676adef1b1.png
[9fd6d10f886149f281b6939c20819fc9.png]: /images/20220828/c22469e411654f78a34eb884b640fc35.png
[e169ac4abef4445da988ba121cf026b7.png]: /images/20220828/d3b89f01a62f4fdbbceb810b789dcac2.png
[523d3ab2e4524f9aa5e42e1bc8700c2a.png]: /images/20220828/6d8a52454adc4bbdb7a1b448cd5bdaac.png
[b759e2cdfaf844e49c9810d9ec1ecb2d.png]: /images/20220828/e85cfc2adf02420e9c2bf483eab6882e.png
[d8a4e8c8afe14cefb1cacef2841ad6f2.png]: /images/20220828/aa9683dbdbd44d2f9ab36b81f5f051e7.png
[52adef81a2214924b8d46c934b4e3c1c.png]: /images/20220828/0ee6197ac630488a87e299f004092875.png
[f27466d28d834ef69092f2df82823451.png]: /images/20220828/bc9ef8c4f6354185a0e5eaeea63588c3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/312ce156ac0e4ed695066547140cd275.png
[0193188f7de149a2b7d2e6eef5e2b5a8.png]: /images/20220828/ada937dad6514d448192921d28d478ee.png
[1563836602374a74b0872aa9c6d99ebd.png]: /images/20220828/e4dc675770b9474a958edc168615fd1e.png
[9be70acf4b2640e39fe97e8e8cd1f3bf.png]: /images/20220828/45b7c2ac452346299b87df68f6f7d3d9.png
[1e189a64027943babd726c0787d37072.png]: /images/20220828/ae273bf8cd484affa480e5a2ea453d8a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a62b8dc12e594ed7a83faa54cf80076d.png
[01e861a397174068a86f9ed3140a0d2a.png]: /images/20220828/c36ab2e8367f43648af7048c9ddd1173.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b99e69d72a1e45788f637781c78a5c51.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/96df861a868546638fc41fcc57988c7e.png