STL六大组件中算法模块sort为啥采用快速排序作为底层思想

我就是我 2022-09-12 02:59 40阅读 0赞

### 文章目录 ###

*  一、面试官发问sort底层采用什么排序
 *  二、三种递归实现和非递归实现代码如下:
 *  三、快速排序的优化方法之三数取中
 *  四、快速排序的时间和空间复杂度

# 一、面试官发问sort底层采用什么排序 #

**当你第一眼看到这道面试题是不是心里在暗喜，一问算法题就比问排序算法，一问排序算法就问快速排序。**

**如果你回答：**

> STL里的sort算法肯定用的是快速排序啊？难不成还是冒泡排序么？

如果你只是回答快速排序，那么恭喜你只答对了33.333%，离正确答案还差一大截。

**回答完，接着会引来一堆问题轰炸：**

*  数据量大和数据量小都适合用快速排序吗？
 *  快速排序的时间复杂度不是稳定的nlogn，最坏情况会变成n^2，怎么解决复杂度恶化问题？
 *  快速排序递归实现时，怎么解决递归层次过深的问题？
 *  递归过深会引发什么问题？
 *  怎么控制递归深度？如果达到递归深度了还没排完序怎么办？

**首先，回答用到哪种排序算法，正确答案是：**

> 毫无疑问是用到了快速排序，但不仅仅只用了快速排序，还结合了插入排序和堆排序。

**是不是很惊喜，很意外？**

为什么？直接看STL源码实现，来源于侯捷大佬翻译的鼎鼎大名的《STL源码剖析》关于sort算法实现的细节，实现细节有很多精彩的地方。

**并非所有容器都使用sort算法:**

> 既然问的是STL的sort算法实现，那么先确认一个问题，哪些STL容器需要用到sort算法？

**首先:**关系型容器拥有自动排序功能，因为底层采用RB-Tree，所以不需要用到sort算法。  
**其次:**序列式容器中的stack、queue和priority-queue都有特定的出入口，不允许用户对元素排序。  
**最后:**剩下的vector、deque，适用sort算法。

**实现逻辑:**

**STL的sort算法，数据量大时采用QuickSort快排算法，分段归并排序。****一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。****如果递归层次过深，还会改用HeapSort堆排序。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_11_color_FFFFFF_t_70_g_se_x_16]  
**结合快速排序-插入排序-堆排序 三种排序算法。**

思考：

**1.为什么对于区间小于16的采用插入排序，如果递归深度恶化改用堆排序？**

插入排序对于基本有序或数据较少的序列很高效。

堆排序的时间复杂度固定为O(nlogn)，不需要再递归下去了。

**2.那堆排序既然也是O(nlogn）直接用堆排序实现sort不行吗？为啥用快速排序实现？**

**第一点:**堆排序数据访问的方式没有快速排序友好。对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。 比如，堆排序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对堆顶节点进行堆化，会依次访问数组下标是 1，2，4，8 的元素，而不是像快速排序那样，局部顺序访问，所以，这样对 CPU 缓存是不友好的。

**第二点:**对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。

# 二、三种递归实现和非递归实现代码如下: #

#define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    #include<algorithm>
    #include<stack>
    using namespace std;
    
    int QuickSort1(int* arr, int begin, int end)  //左右指针法
    { 
    	if (begin >= end)
    	{ 
    		return arr[begin];
    	}
    	int key = arr[begin];
    	int left = begin;
    	int right = end;
    	while (left < right)
    	{ 
    		while (left < right&&arr[right] >= key)
    		{ 
    			right--;
    		}
    		while (left < right&&arr[left] <= key)
    		{ 
    			left++;
    		}
    		std::swap(arr[left], arr[right]);
    	}
    	int meet = left;
    	return meet;
    }
    
    int QucikSort2(int* arr, int begin, int end)  //挖坑法
    { 
    	if (begin >= end)
    	{ 
    		return arr[begin];
    	}
    	int key = arr[begin];
    	int left = begin;
    	int right = end;
    	while (left < right)
    	{ 
    		while (left < right&&arr[right] >= key)
    		{ 
    			right--;
    		}
    		arr[left] = arr[right];
    		while (left < right&&arr[left] <= key)
    		{ 
    			left++;
    		}
    		arr[right] = arr[left];
    	}
    	int meet = left;
    	arr[meet] = key	;
    	return meet;
    }
    
    int QuickSort3(int* arr, int begin, int end)
    { 
    	if (begin >= end)
    	{ 
    		return arr[begin];
    	}
    	int prev = begin;
    	int cur = begin + 1;
    	int key = arr[begin];
    	while (cur <= end)
    	{ 
    		if (arr[cur] < key && (++prev) != cur)
    		{ 
    			std::swap(arr[cur], arr[prev]);
    		}
    		cur++;
    	}
    	int meet = prev;
    	std::swap(arr[prev], key);
    	return meet;
    }
    
    int PartSort(int* arr, int begin, int end)
    { 
    	if (begin >= end)
    	{ 
    		return arr[begin];
    	}
    	int meet = QuickSort1(arr, begin, end);
    	PartSort(arr, begin, meet - 1);
    	PartSort(arr, meet + 1, end);
    }
    
    void QucikSortNonR(int* arr, int begin, int end)
    { 
    	stack<int> st;
    	st.push(begin);
    	st.push(end);
    	while (!st.empty())
    	{ 
    		int left = 0;
    		int right = 0;
    
    		right = st.top();
    		st.pop();
    		left = st.top();
    		st.pop();
    
    		int key = QuickSort1(arr, begin, end);
    		if (left < key - 1)
    		{ 
    			st.push(left);
    			st.push(key - 1);
    		}
    		if (key + 1 < right)
    		{ 
    			st.push(key);
    			st.push(right);
    		}
    	}
    }

# 三、快速排序的优化方法之三数取中 #

**三数取中。在最左端、最右端和中间三个数中选取中数作为key值，这样key值位于较为中间的值的可能性就大大提高。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_18_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]

//三数取中
    int getMid(int *arr, int left, int right)
    { 
    	int mid = left + (right - left) / 2;
    	if (arr[mid] > arr[left])
    	{ 
    		if (arr[mid] < arr[right])
    		{ 
    			return mid;
    		}
    		else if (arr[left]>arr[right])
    		{ 
    			return left;
    		}
    		else
    		{ 
    			return right;
    		}
    	}
    	else
    	{ 
    		if (arr[mid] > arr[right])
    		{ 
    			return mid;
    		}
    		else if (arr[left] < arr[right])
    		{ 
    			return left;
    		}
    		else
    		{ 
    			return right;
    		}
    	}
    }

# 四、快速排序的时间和空间复杂度 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/02f4415cabfa4f8ab6477fe169048fee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/26b46ebdbfef41e09f6e9f008b97e0f1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7b96f0639b194136a7f0e41d5bef8229.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c880763f36084fbcbabf9607dfcbe8ad.png