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/