简单的实现STL Agorithm中的sort函数

刚刚复习完快速排序。实现了一个简单的快速排序，其中还有不少地方可以优化：

1. 三点中值法，在选择三个值并取中间值作为桩。

2. 在元素个数较少时，直接使用插入排序。

突然想起来看看STL中的sort函数是怎样实现的，发现其也使用了这几种优化方法。并结合了堆排序。

下面是我实现的一个简单的STL中的sort，叫做introsort

#include <iostream>#include "heapsort.cpp"using namespace std;#define STL_THRESHOLD 16//阙值，STL中取16//三点中值，取三个数，中间大小的inline const int& median(const int& a, const int& b, const int& c){if(a < b){if(b < c) return b;else if(c < a) return a;else return c;}else{if(b > c) return b;else if(a > c) return c;else return a;}}//交换函数inline void swap(int *A, const int a, const int b){int tmp = A[a];A[a] = A[b];A[b] = tmp;}//控制分支恶化，找出最大的k使得2^k<n。inline int lg(int n){int k;for(k = 0; n > 1; n >>= 1) k++;return k;}//快速排序中的划分函数，使用三点中值法来提高效率int partition(int *A, int start, int end, int key){while (true){ while (A[start] < key) start++;while (A[end] > key) end--;if(start >= end)return start;swap(A, start, end);start++;}}//introsort基本和快速排序相同，只是加入了阙值停止排序，并在分支恶化比较严重时使用堆排序进行子序列的排序void introsort(int *A, int start, int end, int depth_limit){while ((end - start) > STL_THRESHOLD)//长度大于阙值，继续使用快排{if(depth_limit == 0)//深度过深，恶化严重，使用堆排序{heapsort(A, end - start + 1);return;}depth_limit--;int tmp = partition(A, start, end, median(A[start], A[start + (start + end)/2], A[end]));introsort(A, start, tmp - 1, depth_limit);introsort(A, tmp + 1, end, depth_limit);}}//插入排序void insertion_sort(int *A, int start, int end){for(int i = start + 1; i <= end; i++){int j = i - 1;while (A[j] > A[j + 1] && j >= start){swap(A, j, j + 1);j--;}}}inline void sort(int *A, int start, int end){//先使用introsort，当子序列长度小于阙值时，停止排序，这时数组基本有序，再使用插入排序完成剩下的排序if(start < end){introsort(A, start, end, lg(2 * (end - start)));insertion_sort(A, start, end);}}int main(){int A[10] = {10, 5, 1, 8, 4, 2, 6, 12, 7, 2};sort(A, 0, 9);for(int i=0;i<10;i++)cout<<A[i]<<" ";}

其实还有很多地方可以优化，比如在快速排序时使用多线程来帮助分区。