C/C++ 排序 总结（够用就行，没有刻意追求标准）1. qsort() (include stdlib.h)qsort() 采用的是快速排序首
C/C++ 排序 总结 （够用就行，没有刻意追求标准）
1. qsort() (include <stdlib.h>)
qsort() 采用的是快速排序
首先要说的是c 语言中的qsort()，不建议使用qsort()，因为
STL（标准模板库）中的sort() 和 qsort() 的核心都是快速排
序，通常用sort() 就行了。
函数原型：
void qsort ( void * base,
size_t num,
size_t size,
int ( * comparator ) ( const void *, const void * ) );//第四个参数可以缺省
base : 待排序数组的首地址
num ：待排序元素的个数
size ：每个元素的大小(byte), 用sizeof(a[0])即可，a为待排序数组
comparator： 比较函数指针
一个简单的调用：（a 为数组名，给十个元素排序）
qsort(a, 10, seizeof(a[0])); //第四个参数默认，适用于基本类型的升序
qsort(a, 10, seizeof(a[0]), compare);
比较函数可以如下：
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
个人的理解：比较函数返回第一个元素减去第二个元素，为升序
排列。反之，降序。
/* qsort example */#include <stdio.h>#include <stdlib.h>int values[] = { 40, 10, 100, 90, 20, 25 };int compare (const void * a, const void * b){ return ( *(int*)a - *(int*)b ); //升序排列;调换减数、被减数，则为降序}int main (){ int n; qsort (values, 6, sizeof(int), compare); for (n=0; n<6; n++) printf ("%d ",values[n]); return 0;}
2. sort()（#include <algorithm>)
sort() 目前采用的是加强版的快速排序， 是结合内插排序的快速排序
目的在于克服快速排序在最初情况（元素基本有序）的效率底下。
函数原型：
template <class RandomAccessIterator, class Compare>
void sort ( RandomAccessIterator first,
RandomAccessIterator last,
Compare comp ); //第三个参数可以缺省
看起来有点复杂，刚开始我们可以去弱化这个函数原型，把参数都
当成指针理解：
first：待排序序列首地址指针
last ：该指针指向最后一个元素的后边
comp ：比较函数指针
一个简单的调用：（a 为数组名，给十个元素排序）
sort(a, a + 10); //比较函数使用默认的，适用于基本类型升序
sort(a, a + 10, compare) //自己提供比较函数
比较函数可以如下：
bool compare (int a, int b)
{
return a < b; //升序;返回a > b，则为降序
}
个人的理解：比较函数返回第一个元素小于第二个元素，为升序
排列。反之，降序。注意这个返回值为bool型。
3. stable_sort() (include <algorithm>)
stable_sort() 采用的是归并排序
stable_sort() 和 sort() 的参数说明、用法完全相同，只不过
stable_sort() 为稳定排序，即相等元素的相对顺序在排序后不
变。有点乱吧，看个例子就会明白的
// stable_sort example#include <iostream>#include <algorithm>#include <vector>using namespace std;bool compare_as_ints (double i,double j){ return (int(i)<int(j));}int main () { double mydoubles1[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58}; cout << "using default comparison:"; stable_sort (mydoubles1, mydoubles1 + 8); for (int i = 0; i < 8; i++) cout<<" "<<mydoubles1[i]; double mydoubles2[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58}; cout << "\nusing 'compare_as_ints' :"; stable_sort (mydoubles2, mydoubles2 + 8, compare_as_ints); for (int i = 0; i < 8; i++) cout<<" "<<mydoubles2[i]; cout << endl; return 0;}Output :
4.partial_sort() (include <algorithm>)
partial_sort() 采用的是堆排序
函数原型：
template <class RandomAccessIterator, class Compare>
void partial_sort ( RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp ); //第四个参数可以缺省
功能：排序后[first,middle) 中的元素都小于[middle, last) 中的元素
但这两个区间中的元素都无序
一个简单的调用：（a 为数组名，假设有12个元素）
partial_sort (a, a + 5, a + 12); //比较函数使用默认的，适用于基本类型升序
//前五个元素均小于后边的每个元素，即找出最小的5个元素
partial_sort (a, a + 5, a + 12, compare) //自己提供比较函数
如果希望用partial_sort来实现全排序，只要让middle=last就可以了。
5.nth_element() (include <algorithm>)
nth_element() 和 partial_sort() 的参数说明、用法完全相同，把
partial_sort() 中的第二个参数改名为：nth
执行结果： nth 位置的元素就为待排序序列中的第n 个元素
一个简单的调用：（a 为数组名，假设有12个元素）
nth_element(a, a + 5, a + 12); //比较函数使用默认的，适用于基本类型升序
//a[5] 即为数组中第六小元素，注意是第六小
nth_element(a, a + 5, a + 12, compare) //自己提供比较函数
总结 选择合适的排序函数
--------------------------------------------
为什么要选择合适的排序函数？可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小， 因此你觉得随便用哪个函数都无关紧要。
其实不然，即使你不关心效率，如果你选择合适的排序函数，你会让你的代码更容易让人明白，你会让你的代码更有扩充性，逐渐养成一个良好的习惯，很重要吧 。
如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较，那我告诉你，qsort和sort是一样的，因为他们采用的都是快速排序。从效率上看，以下几种sort算法的是一个排序，效率由高到低（耗时由小变大）：
partion
stable_partition
nth_element
partial_sort
sort
stable_sort
记得，以前翻译过Effective STL的文章，其中对如何选择排序函数总结的很好：
若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；
若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选.
若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序，nth_element是最理想的；
若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；
若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。正如上面介绍的有几种方式可以选择。
总之记住一句话： 如果你想节约时间，不要走弯路, 也不要走多余的路!
参考文献：
1.李忠军博 http://blogold.chinaunix.net/u/21813/showart_211598.html
2.c++在线文档http://www.cplusplus.com/
