STL有关排序的几个函数如下所示，需要更少资源（时间和空间）的算法列在需要更多的前面，需要指出的是他们完成的工作是不一样的。
1. partition 4. partial_sort 2. stable_partition 5. sort 3. nth_element 6. stable_sort
个人笔记：
在快速排序中，切分函数是基本操作，那么在往后和往前移动的过程中存在边界判断的需要，由于排序中的这种边界判断，处在底层，如果能够取消，将极大提升效率，对此要有一定认识。特别注意，low<len-1 这样的边界判断有时是不需要的。之所以判断边界，是因为有可能容器中所有的元素都小于（或不小于）枢轴，也即都满足判断条件，会导致越界。这跟枢轴选取的方式有关系，如果可以断定枢轴会在待排序区出现，那么很大可能不会越界，这取决于等于枢轴是否满足调整条件。
一、partition
主要功能是将数据分成两部分，一部分满足条件，另一部分不满足条件。满足与否，是通过一个返回bool量的单参数函数实现的。
#include<iostream> #include<vector> 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<int> &vec,bool (*pred)(int)) //通过函数指针传入 { int len = vec.size(); if (len < 2) return 0; int low = 0; int hi = len - 1; while (true) { while ((low<len-1)&&(*pred)(vec[low])) //存在边界判断 { low++; } while ((hi>0) && !((*pred)(vec[hi]))) { hi--; } if (low >= hi) break; swap(vec[low],vec[hi]); } return low; } void myprint(const vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> 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<iostream> #include<vector> using namespace std; void swap(int &a, int &b) { int temp; temp = a; a = b; b = temp; } int partition(vector<int> &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<int> &vec, int num) { int len = vec.size(); int low = 0; int hi = len - 1; while (low<hi) { int j = partition(vec,low,hi); if (j == num - 1) return; else if (j < num - 1) low = j+1; else hi = j - 1; } } void myprint(const vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> data = { 11,5, 4, 7, 6, 8, 1,10 }; myprint(data); nth_element(data,2); myprint(data); system("pause"); return 0; }三、partial_sort
void partial_sort(vector<int> &vec,int len) 将最小的前len个数放到数组最前面，并保持有序
局部排序的原理是，建立一个len大小的堆，初始时堆中数据就是数组的前len个数据，将剩余的数据逐个与堆顶的数据比较，如果小于堆顶数据，则交换，并调整堆，最后对堆进行排序。此方案可以实现nth_element函数，差别仅在于有没有最后一步排序。
#include<iostream> #include<vector> using namespace std; void swap(int &a, int &b) { int temp; temp = a; a = b; b = temp; } void adjustHeap(vector<int> &vec,int len,int i) { int max = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left<len && vec[left]>vec[max]) max = left; if (right<len && vec[left]>vec[max]) max = right; if (max != i) { swap(vec[i],vec[max]); adjustHeap(vec, len, max); } } void buildHeap(vector<int> &vec,int len) { if (len < 2) return; for (int i = len / 2 - 1; i >= 0; i--) { adjustHeap(vec, len, i); } } void sortHeap(vector<int> &vec,int len) { for (int i = len - 1; i>0; i--) { swap(vec[0],vec[i]); adjustHeap(vec,i,0); } } void partial_sort(vector<int> &vec,int len) { buildHeap(vec,len); for (int i = len; i < vec.size(); i++) { if (vec[0]>vec[i]) swap(vec[0], vec[i]); adjustHeap(vec,len,0); } sortHeap(vec,len); } void myprint(const vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> data = { 11,5, 4, 7, 6, 8, 1,10 }; myprint(data); partial_sort(data, 4); myprint(data); system("pause"); return 0; }