本文共 3659 字，大约阅读时间需要 12 分钟。

     STL有关排序的几个函数如下所示，需要更少资源（时间和空间）的算法列在需要更多的前面，需要指出的是他们完成的工作是不一样的。

1. partition                  4. partial_sort

个人笔记：

        在快速排序中，切分函数是基本操作，那么在往后和往前移动的过程中存在边界判断的需要，由于排序中的这种边界判断，处在底层，如果能够取消，将极大提升效率，对此要有一定认识。特别注意，low<len-1 这样的边界判断有时是不需要的。之所以判断边界，是因为有可能容器中所有的元素都小于（或不小于）枢轴，也即都满足判断条件，会导致越界。这跟枢轴选取的方式有关系，如果可以断定枢轴会在待排序区出现，那么很大可能不会越界，这取决于等于枢轴是否满足调整条件。

一、partition

主要功能是将数据分成两部分，一部分满足条件，另一部分不满足条件。满足与否，是通过一个返回bool量的单参数函数实现的。

#include
   
    #include
    
     using namespace std;void swap(int &a,int &b){	int temp;	temp = a;	a = b;	b = temp;}bool fun(int a)   //判别函数{	int key = 5;	return a < key;}int partition(vector
     
       &vec,bool (*pred)(int))  //通过函数指针传入{	int len = vec.size();	if (len < 2) return 0;	int low = 0;	int hi = len - 1;	while (true)	{		while ((low
      
       0) && !((*pred)(vec[hi])))		{			hi--;		}		if (low >= hi) break;		swap(vec[low],vec[hi]);	}	return low;}void myprint(const vector
       
         a){	for (int i = 0; i < a.size(); i++)	{		cout << a[i] << " ";	}	cout << endl;}int main(){	vector
        
          data = {2,4,7,8,1}; myprint(data); partition(data,fun); myprint(data); system("pause"); return 0;}
        
       
      
     
    
   

二、nth_element

     void nth_element(vector<int> &vec, int num)   将最小（或最大）的num个数放在数组的开始处。注意num个数是无序的。

     主要是利用快速排序的切分操作，源码针对枢轴的选取了优化措施（取待处理区间首、中间、尾3个值中的中间值作为枢轴，防止切分操作退化），这里为了简化，没有对枢轴的选取进行优化。

      根据切分函数的返回值，判断是否达到了找出了num个满足要求的数，如果不满足，判断下一处理区间。

#include
   
    #include
    
     using namespace std;void swap(int &a, int &b){	int temp;	temp = a;	a = b;	b = temp;}int partition(vector
     
       &vec,int low,int hi){	int mid = (hi - low) / 2 + low;	int pivot = vec[low];	int i = low + 1;	int j = hi;	while (true)	{		while (i < hi && vec[i] < pivot) i++;		while (j>low && vec[j]>pivot) j--;		if (i >= j) break;		swap(vec[i], vec[j]);		i++;		j--;	}	swap(vec[low],vec[j]);	return j;}void nth_element(vector
      
        &vec, int num){	int len = vec.size();	int low = 0;	int hi = len - 1;	while (low