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

x33g5p2x  于11个月前 转载在 其他  
字(3.2k)|赞(0)|评价(0)|浏览(137)

一、面试官发问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堆排序。

结合快速排序-插入排序-堆排序 三种排序算法。

思考:

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值位于较为中间的值的可能性就大大提高。

//三数取中
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;
		}
	}
}

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

相关文章