一、面試官發問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;
		}
	}
}

四、快速排序的時間和空間復雜度