## STL经典算法集锦<八>之IntroSort STL的sort算法的优化策略： 1、  数据量大时采用QuickSort，分段递归排序。 2、  一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来的额外负荷，就改用Insertion Sort。 3、  如果层次过深，还会改用HeapSort 4、  “三点中值”获取好的分割 IntroSort的实现代码为： ~~~ //数据量的分界线，决定了使用quick sort/heap sort还是insertion sort const int threshold=16; //堆排序用到的辅助函数 int parent(int i) { return (int)((i-1)/2); } int left(int i) { return 2 * i+1; } int right(int i) { return (2 * i + 2); } void heapShiftDown(int heap[], int i, int begin,int end) { int l = left(i-begin)+begin; int r = right(i-begin)+begin; int largest=i; //找出左右字节点与父节点中的最大者 if(l < end && heap[l] > heap[largest]) largest = l; if(r < end && heap[r] > heap[largest]) largest = r; //若最大者不为父节点，则需交换数据，并持续向下滚动至满足最大堆特性 if(largest != i) { swap(heap[largest],heap[i]); heapShiftDown(heap, largest, begin,end); } } //自底向上的开始建堆，即从堆的倒数第二层开始 void buildHeap(int heap[],int begin,int end) { for(int i = (begin+end)/2; i >= begin; i--) { heapShiftDown(heap, i, begin,end); } } //堆排序 void heapSort(int heap[], int begin,int end) { buildHeap(heap,begin,end); for(int i = end; i >begin; i--) { swap(heap[begin],heap[i]); heapShiftDown(heap,begin,begin, i); } } //插入排序 void insertionSort(int array[],int len) { int i,j,temp; for(i=1;i<len;i++) { temp = array[i];//store the original sorted array in temp for(j=i;j>0 && temp < array[j-1];j--)//compare the new array with temp(maybe -1?) { array[j]=array[j-1];//all larger elements are moved one pot to the right } array[j]=temp; } } //三点中值 int median3(int array[],int first,int median,int end) { if(array[first]<array[median]) { if(array[median]<array[end]) return median; else if(array[first]<array[end]) return end; else return first; } else if(array[first]<array[end]) return first; else if(array[median]<array[end]) return end; else return median; } //对数组分割 int partition(int array[],int left,int right,int p) { //选择最右侧的元素作为分割标准 int index = left; swap(array[p],array[right]); int pivot = array[right]; //将所有小于标准的点移动到index的左侧 for (int i=left; i<right; i++) { if (array[i] < pivot) swap(array[index++],array[i]); } //将标准与index指向的元素交换，返回index，即分割位置 swap(array[right],array[index]); return index; } //递归的对数组进行分割排序 void introSortLoop(int array[],int begin,int end,int depthLimit) { while((end-begin+1)>threshold) //子数组数据量大小，则交给后面的插入排序进行处理 { if(depthLimit==0) //递归深度过大，则由堆排序代替 { heapSort(array,begin,end); return ; } --depthLimit; //使用quick sort进行排序 int cut=partition(array,begin,end, median3(array,begin,begin+(end-begin)/2,end)); introSortLoop(array,cut,end,depthLimit); end=cut; //对左半段进行递归的sort } } //计算最大容忍的递归深度 int lg(int n) { int k; for(k=0;n>1;n>>=1) ++k; return k; } //霸气的introsort void introSort(int array[],int len) { if(len!=1) { introSortLoop(array,0,len-1,lg(len)*2); insertionSort(array,len); } } ~~~ 注：更多关于STL原版IntroSort的实现的可以参考： [http://blog.csdn.net/xinhanggebuguake/article/details/7547066](http://blog.csdn.net/xinhanggebuguake/article/details/7547066) 结篇想说的话：从去年二月份开始看《STL源码剖析》，到今年年初看SGI STL2.91版本的代码，再到最近亲自把所有重点代码自己实现，此期间经历了太长的时间。当然在学习STL的过程中自己也取得了长足的进步。STL之经典毋庸置疑，经历了书籍，源码，自己实现的一个过程，觉得能把这个过程坚持下来的人不会太多，而自己是其中一个，怎能不骄傲。在这个找实习的季节里屡屡倍受打击，也只有这样的一份坚持，让我坚信付出终有回报，加油。

## STL经典算法集锦<七>之随机洗牌（random_shuffle） 将一个数组中的元素序列打算顺序进行重排，并需要保证重排后的每一种结果是等概率且随机的。下面的两种算法哪一种是正确的？（注：random(a,b)返回一个a~b的随机整数） 1. for i=1 to n do swap( a[i], a[random(1,n)] ); 2. for i=1 to n do swap( a[i], a[random(i,n)] ); **解释：** 首先，1～n的序列打乱重排共有n!个不同的排列，且每种排列被选中的概率为1/N!，只有这样的算法才是等概率且随机的。   第一种算法将会产生n^n种情况，显然其中出现了重复的情况。那么会不会虽然出现重复，但每种排列重复的次数相同，所以算法依然是等概率且随机的呢？答案是，不会。 假设上述情况成立，则n^n必定n!整除。但是，绝大多数情况下，n!的质因子远多于n^n的质因子（即n的质因子）。根据Bertrand-Chebyshev定理，在n/2和n之间一定还有一个质数。这两个质数的乘积已经大于n了。搞了半天，第一种看似对称而美观的算法居然是错的！即对所有大于2的n，上述整除都不不可能的。   第二种算法是符合要求的随机洗牌算法。 使用数学归纳法证明： 1、当n=1时，所以元素arr[0]在任何一个位置的概率为1/1，命题成立。 2、假设当n=k时，命题成立，即原数组中任何一个元素在任何一个位置的概率为1/k。 3、则当n=k+1时，当算法执行完k次时，前k个元素在前k个位置的概率均为1/k。当执行最后一步时，前k个元素中任何一个元素被替换到第k+1位置的概率为：(1-1/(k+1)) * 1/k = 1/(k+1); 在前面k个位置任何一个位置的概率为(1-1/(k+1)) * 1/k = 1/(k+1);故前k个元素在任意位置的的概率都为1/(k+1)所以，对于前k个元素，它们在k+1的位置上概率为1/(k+1)。对于第k+1个元素，其在原位置的概率为1/k+1，在前k个位置任何一个位置的概率为：(1-k/（k+1)） * (1/k)=1/（k+1），所以对于第k+1个元素，其在整个数组前k+1个位置上的概率也均为1/k+1。  综上所述，对于任意n，只要按照方案中的方法，即可满足每个元素在任何一个位置出现的概率均为1/n。   解释完了洗牌算法的原理，那下面就是自己实现的random_shuffle的代码。 ~~~ void swap(int& a,int& b)//不要尝试用“抑或”运算完成元素的交换，详见抑或运算 { int temp=b; b=a; a=temp; } void randomShuffle(int array[], int len) { for(int i=1;i<len;i++) { int j=rand()%(i+1); swap(array[i],array[j]); } } ~~~ 注：本文解释部分参考了以下文章： [http://hi.baidu.com/wulei407/blog/item/b6ea451b6572f9fdaf513315.html](http://hi.baidu.com/wulei407/blog/item/b6ea451b6572f9fdaf513315.html) [http://blog.chinaunix.net/uid-20196318-id-216658.html](http://blog.chinaunix.net/uid-20196318-id-216658.html)

## STL经典算法集锦<六>之排列（next_permutation/prev_permutation） STL中涉及到数组的排列的有两个函数，即next_permutation/prev_permutation，分别用于求上一个以及下一个排列。两函数的算法使用的原理大体相同。以next_permutation为例，列出算法并解释。 **算法：** 首先，从最为段开始往前寻找两个相邻的元素，令第一个元素索引为endi第二个元素索引为endii，且满足array[endi]<array[endii]。然后，再从最尾端开始向前检测，找到第一个大于array[endi]的元素，令其为索引j。将元素array[endi],array[j]对调，然后将endii之后的所有元素颠倒排列。即求的下一个排列。 **解释：** 一、如果数组k以后的是一个递减序列，则仅依靠调换k以后的元素不可能完成任务，所以必须找到满足k>k+1的元素，即保证k以后的序列不递减。 二、满足一之后，那么下一个序列的第k位一定是从后面找到刚好比a[k]大的一个比a[k]大的一个数打头的（为了保证刚好大于，又k+1之后的元素递减，所以从数组尾开始找到第一个比a[k]大的元素即可满足要求）。将这个数的索引记为j。 三、将a[j]与a[k]对调。此时，j后面的元素是降序的。所以需要把j后面的逆转一下，从降序到升序，如此就得到了恰好比之前序列大一号的序列。 代码：next_permutation ~~~ bool nextPermutation(int array[],int len) { int endi=len-1; int endii; if(len==1)return false; while(true) { endii=endi; endi--; if(array[endi]<array[endii])// 如果前一个元素小于后一个元素 { int j=len; while(array[--j]<array[endi]);// 由尾端往前找，直到遇上比array[endi]大的元素 swap(array[j],array[endi]); // 交换找到的元素 reverse(array+endii,array+len-1);// 将 endii 之后的元素全部逆向重排 return true; } if(endi==0)//排列已至最大，无下一个排列 { reverse(array,array+len-1); return false; } } } ~~~ 代码：prev_permutation ~~~ bool prevPermutation(int array[],int len) { int endi=len-1; int endii; if(len==1)return false; while(true) { endii=endi; endi--; if(array[endi]>array[endii])// 如果前一个元素大于后一个元素 { int j=len; while(array[--j]>array[endi]);// 由尾端往前找，直到遇上比array[endi]小的元素 swap(array[j],array[endi]); // 交换找到的元素 reverse(array+endii,array+len-1);// 将 endii 之后的元素全部逆向重排 return true; } if(endi==0)//排列已至最小，无上一个排列 { reverse(array,array+len-1); return false; } } } ~~~

## STL经典算法集锦<五>之查找（lower_bound/upper_bound/binary_search） 这三个算法都比较的常用，而且具有一定的相似的性。理论依据也很明显，下面就直接贴出自己的实现版本。其中lower_bound与upper_bound实现了两个版本。版本一与STL的实现方法完全相同，以数据的总长度折半，版本二则是直接取前后的中点。当然本质上没有太大区别。 **lower_bound版本一：** ~~~ int lowerBound(int array[],int left,int right,int value) { int mid=0,half=0; int len=(right+left+1)/2; while(len>0) { half=len>>1; //数据长度折半 mid=left+half; //计算中点 if (array[mid]<value) //调整总长与起点 { len=len-half-1; left=mid+1; } else len=half; } return left; } ~~~ **lower_bound版本二：** ~~~ int lowerBound(int array[],int left,int right,int value) { int mid=0; while(left<right) { mid=(right+left)/2; //计算中点 if (array[mid]<value) //调整起点或者终点 left=mid+1; else right=mid; } return right; } ~~~ **upper_bound版本一：** ~~~ int upperBound(int array[],int left,int right,int value) { int mid=0,half=0; int len=(right+left+1)/2; while(len>0) { half=len>>1; //长度折半 mid=left+half; //计算中点 if (array[mid]>value) //调整长度与起点 len=half; else { len=len-half-1; left=mid+1; } } return left; } ~~~ **upper_bound版本二： ** ~~~ int upperBound(int array[],int left,int right,int value) { int mid=0; while(left<right) { mid=(right+left)/2; //计算中点 if (array[mid]>value) //调整起点或者终点 right=mid; else left=mid+1; } return right; } ~~~ **折半查找：** ~~~ int binarySearch(int array[],int left,int right,int value) { int mid; while(left<=right) { mid=(left&right)+((left^right)>>1); //防止溢出 if(array[mid]==value) return mid; else if (array[mid]<value) left=mid+1; else right=mid-1; } return -1; } ~~~ **可用测试代码：** ~~~ int main() { srand(time(0)); int len=21; int array[len]; for(int i=0;i<len;i++) array[i]=rand()%200; sort(array,array+len); for(int i=0;i<len;i++) cout<<array[i]<<"\t"; cout<<endl; cout<<"\nresult:"<<binarySearch(array,0,len-1,33)<<endl; return 0; } ~~~

## STL经典算法集锦<四>之rotate STL在rotate上的优化是极尽其所能的。分别对前向访问，双向访问，随机访问的数据结构实现了三个版本的rotate。下面是自己按照对三种算法的理解，自己进行的实现。实现中我尽力避免使用C++的特性，从而以后可以在纯C的代码中使用。 下面是我使用到的数据结构，单向链表与双向链表，用于实现算法和验证算法的正确性： ~~~ //单链表节点 typedef struct Node* Link; struct Node{ int value; Link next; Link forward(Link& i) { i=i->next; return i; } void swap(Link& i) { int temp=i->value; i->value=this->value; this->value=temp; } }; typedef struct BiNode* BiLink; struct BiNode{ int value; BiLink next; BiLink prev; BiLink forward(BiLink& i) { i=i->next; return i; } BiLink backward(BiLink& i) { i=i->prev; return i; } void swap(BiLink& i) { int temp=i->value; i->value=this->value; this->value=temp; } }; ~~~ 版本一：forward iterator,即类单向链表上的rotate ~~~ //forward iterator,即类单向链表 void forwardRotate(Link head,Link middle) { Link i=middle; while(true) { head->swap(i); head->forward(head); i->forward(i); if(head==middle) { if(i==NULL) return ; //如果前后两指针同时到达末尾，则结束 middle=i; //如果前者先到达末尾，则将i作为middle，继续rotate } else if(i==NULL) i=middle; //如果后者先到达末尾，则将middle作为i，继续rotate } } ~~~ 另附上注释的图像版以帮助理解：  版本二：bidirection iterator,即类双向链表上的rotate 这个版本的算法很容易理解，即是分段进行反转，之后对左右数据进行反转，代码如下： ~~~ void reverse(BiLink first,BiLink last) { while(first!=last &&first!=last->backward(last)) { last->swap(first); first->forward(first); } } void bidirectionRotate(BiLink first,BiLink middle,BiLink last) { reverse(first,middle); reverse(middle,last); reverse(first,last); } ~~~ 版本三：random access iterator,即类数组上的rotate 该版本的效率无疑是最高的，当然算法因为涉及到有关群论的知识所以有点难以理解。其理论支持详见：[数组循环移位问题](http://blog.csdn.net/xinhanggebuguake/article/details/7498471) 自己实现版本的代码如下： ~~~ //求最大公约数 int gcd(int m,int n) { int t; while(n!=0) { t=m%n; m=n; n=t; } return m; } //循环移位 void rotate_cycle(int array[],int len,int initial,int shift) { int value=array[initial]; int first=initial; int next=initial+shift; while(next!=initial) { array[first]=array[next]; first=next; next=(next+shift)%len; } array[first]=value; } void randomRotate(int array[],int middle,int len) { int n=gcd(len,middle); while(n--) rotate_cycle(array,len,n,middle); } ~~~  最后附上我自己的测试代码： ~~~ int main() { int len=20; srand(time(0)); //单向访问链表的rotate Link head=new Node; head->value=25; cout<<head->value<<"\t"; Link p=head; Link middle; for(int i=0;i<len;i++) { Link next=new Node; p->next=next; next->value=rand()%200; cout<<next->value<<"\t"; if(i==len/4*3) middle=p; p=p->next; } cout<<endl; p->next=NULL; forwardRotate(head,middle); p=head; while(p!=NULL) { cout<<p->value<<"\t"; p=p->next; } cout<<endl; //双向链表的rotate BiLink bihead=new BiNode; bihead->value=25; cout<<bihead->value<<"\t"; BiLink bip=bihead; BiLink bimiddle; for(int i=0;i<len;i++) { BiLink binext=new BiNode; bip->next=binext; binext->prev=bip; binext->value=rand()%200; cout<<binext->value<<"\t"; if(i==len/4) bimiddle=bip; bip=bip->next; } cout<<endl; BiNode end; bip->next=&end; end.prev=bip; bidirectionRotate(bihead,bimiddle,&end); bip=bihead; while(bip!=&end) { cout<<bip->value<<"\t"; bip=bip->next; } cout<<endl; int array[len]; for(int i=0;i<len;i++) { array[i]=rand()%200; cout<<array[i]<<"\t"; } cout<<endl; randomRotate(array,len/3,len); for(int i=0;i<len;i++) cout<<array[i]<<"\t"; cout<<endl; return 0; } ~~~ OK，大致如此了。三个版本的rotate，极至的优化手段，这也许就是STL的魅力所在吧。

## STL经典算法集锦<三>之partition与qsort STL的分割算法主要使用了仿函数来实现。而此处的分割则不，此处实现了两种形式的分割算法：非随机分割算法、随机分割算法(随机算法是在非随机算法的基础上封装而成)。而快速排序则只需简单依赖分割算法就能实现。 **非随机分割算法：** ~~~ int partition(int array[],int left,int right) { //选择最右侧的元素作为分割标准 int index = left; int pivot = array[right]; //将所有小于标准的点移动到index的左侧 for (int i=left; i<right; i++) { if (array[i] < pivot) swap(array[index++],array[i]); } //将标准与index指向的元素交换，返回index，即分割位置 swap(array[right],array[index]); return index; } ~~~ **随机分割算法：** ~~~ int random(int floor,int ceil) { srand(time(0)); return floor+random()%(ceil-floor+1); } int randomizedPartition(int array[],int left,int right) { //随机一个元素作为分割的标准 int i=random(left,right); //将标准移动到最右侧 swap(array[right],array[i]); partition(array,left,right); } ~~~ **快速排序：** ~~~ void qsort(int array[],int left,int right) { if(left<right) { int mid; //mid=randomizedPartition(array,left,right); mid=partition(array,left,right); qsort(array,left,mid-1); qsort(array,mid+1,right); } } ~~~ 两种形式的分割算法的单词输出为： 非随机算法：  随机算法： 

## STL经典算法集锦<二>之堆算法 堆算法主要包括建立最大堆和堆排序算法。所使用建堆的数组将以0开始存储数据。 下面将以两种方法建堆：自底向上的建堆（STL和算法导论中使用到的）、自顶向下建堆（即插入建堆的方法） 公共操作： ~~~ int parent(int i) { return (int)((i-1)/2); } int left(int i) { return 2 * i+1; } int right(int i) { return (2 * i + 2); } ~~~ **版本一：自底向上** ~~~ void heapShiftDown(int heap[], int i, int heap_size) { int l = left(i); int r = right(i); int largest=i; //找出左右字节点与父节点中的最大者 if(l < heap_size && heap[l] > heap[largest]) largest = l; if(r < heap_size && heap[r] > heap[largest]) largest = r; //若最大者不为父节点，则需交换数据，并持续向下滚动至满足最大堆特性 if(largest != i) { swap(heap[largest],heap[i]); heapShiftDown(heap, largest, heap_size); } } //自底向上的开始建堆，即从堆的倒数第二层开始 void buildHeap(int heap[],int heapSize) { for(int i = (heapSize-1)/2; i >= 0; i--) { heapShiftDown(heap, i, heapSize ); } } ~~~ **版本二：自顶向下的建堆** ~~~ //i为新插入节点的位置 void heapShiftUp(int heap[], int i) { int p=parent(i); //判断插入新节点后是否满足最大堆 //否则交换数据并持续向上滚动 if( heap[i] > heap[p]) { swap(heap[i],heap[p]); if(p != 0) heapShiftUp(heap,p); } } void buildHeap(int heap[],int heapSize) { //自第二层开始建堆 for(int i = 1; i < heapSize; i++) { heapShiftUp(heap, i); } } ~~~ **堆排序：** ~~~ void heapSort(int heap[], int heapSize ) { buildHeap(heap,heapSize); for(int i = heapSize- 1; i > 0; i--) { swap(heap[0],heap[i]); heapShiftDown(heap, 0, i); } } ~~~ **测试代码：** ~~~ int main() { int len=20; int array[len]; srand(time(0)); for(int i=0;i<len;i++) array[i]=rand()%200; heapSort(array,len); for(int i=0;i<len;i++) cout<<array[i]<<"\t"; return 0; } ~~~ 单次运行结果： 自底向上：  自顶向下： 

## STL经典算法集锦<一>之list::sort 算法中使用到的数据结构： ~~~ typedef struct Node* Link; struct Node{ int value; Link next; }; ~~~ 算法代码： ~~~ //链表的归并 void merge(Link& first,Link& second) { Node newHead; Link temp=&newHead; while(first!=NULL&&second!=NULL) { if(first->value<=second->value) { temp->next=first; first=first->next; } else { temp->next=second; second=second->next; } temp=temp->next; } if(first!=NULL) { while(first!=NULL) { temp->next=first; first=first->next; temp=temp->next; } } else { while(second!=NULL) { temp->next=second; second=second->next; temp=temp->next; } } first=newHead.next; } //声明为引用类型，以head始终指向链表头而不是原链表的头节点 void mergeSort(Link& head) { //用于存放已序的链表的指针数组 Link array[64]; int fill=0; while(head!=NULL) { int i=0; //每次分割出单个节点 Link p=head; head=head->next; p->next=NULL; //向上滚动的条件是链表array[i]元素个数满足2^n //持续向上滚动合并,直至该array[i]中的数据为空不足以持续向上滚动合并 while(i<fill&&array[i]!=NULL) { merge(array[i],p); swap(p,array[i++]); } swap(p,array[i]); if(i==fill) fill++; } //将所有已序链表归并 for(int i=0;i<fill;i++) merge(head,array[i]); } ~~~ 验证代码： ~~~ #include <iostream> #include <cstdlib> using namespace std; int main() { int len=20; srand(time(0)); Link head=new Node;//构造链表头 head->value=25; cout<<head->value<<"\t"; Link p=head; //随机创建一个链表 for(int i=0;i<len;i++) { Link next=new Node; p->next=next; next->value=rand()%200; cout<<next->value<<"\t"; p=p->next; } cout<<endl; p->next=NULL; //调用归并排序 mergeSort(head); //输出排序后的结果 p=head; while(p!=NULL) { cout<<p->value<<"\t"; p=p->next; } return 0; } ~~~ 单次输出：  

## STL经典算法集锦 所谓经典算法是指STL中有一定的复杂性并且又经常用到的算法。其他算法多是较为容易，利用STL操作很容易实现就不在此之列了。 共计15个算法，包括： > 1、list::sort > 2、heap > 3、partition > 4、rotate(链表版，数组版，即random_access_iterator、bidirection_iterator) > 5、search_n > 6、lower_bound > 7、upper_bound > 8、binary_search > 9、next_permutation > 10、prev_permutation > 11、random_shuffle > 12、Introsort(即顺序表的sort) > 13、_nth_element > 14、Inplace_merge >[info] 15、mergesort 将上述算法列出以收藏和稍后将上述亲自实现。

> 原文出处：[STL经典算法我实现](http://blog.csdn.net/column/details/sgistl.html) 作者：[cyningsun](http://blog.csdn.net/cyningsun) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # STL经典算法我实现 > 囊括所有STL经典的算法，完全不涉及C++高级特性的自我实现。剖析STL的内在魅力，将经典算法扩展到C中去。