一.qsort（）函數

功 能： 使用快速排序例程進行排序
頭文件：stdlib.h
用 法： void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
參數： 1 待排序數組首地址
      2 數組中待排序元素數量
      3 各元素的占用空間大小
      4 指向函數的指針，用于確定排序的順序

復制

qsort（即，quicksort）主要根據你給的比較條件給一個快速排序，主要是通過指針移動實現排序功能。排序之后的結果仍然放在原來數組中。

其中qsort和compare的用法如下：

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )

int compare (const void *elem1, const void *elem2 ) ;

復制

1、對int類型數組排序

compare函數：

int compare(const void *a , const void *b )

{

  return *(int *)a - *(int *)b;  //升序排序

//return *(int *)b - *(int *)a; //降序排序

/*可見：參數列表是兩個空指針，現在他要去指向你的數組元素。所以轉型為你當前的類型，然后取值。

        升序排列時，若第一個參數指針指向的“值”大于第二個參數指針指向的“值”，則返回正；
        若第一個參數指針指向的“值”等于第二個參數指針指向的“值”，則返回零；
        若第一個參數指針指向的“值”小于第二個參數指針指向的“值”，則返回負。

        降序排列時，則剛好相反。
*/
}

復制

?測試實例：

#include<iostream>
#include<stdlib.h>
using namespace std;

int compare(const void *a,const void *b)
{
     return *(int*)b-*(int*)a;  //降序排列
}

int main()
{
     int a[ ]={2,4,1,23,5,76,0,43,24,65};
	 int i;
	 int length = sizeof(a)/sizeof(int);

     for(i=0;i<length;i++)
        cout<<a[i]<<" ";
	 cout<<endl;

     qsort(a,length,sizeof(int),compare);

     for(i=0;i<length;i++)
        cout<<a[i]<<" ";
	 cout<<endl;
     return 0;
}

復制

?2.對char類型數組排序（同int類型）

char word[100];
int compare( const void *a , const void *b )
{

//注意，網上很多版本是 “ return *(char *)a - *(int *)b;  ” 

//注意： *(int *)b是錯誤的用法

//應該是return *(char *)a - *(char *)b;

return *(char *)a - *(char *)b;
}

qsort(word,100,sizeof(word[0]),compare);

復制

3.對double類型數組排序

double in[100];
int compare( const void *a , const void *b )
{

return *(double *)a > *(double *)b ? 1 : -1;

//返回值的問題，顯然compare返回的是一個整型，所以避免double返回小數而被丟失，用一個判斷返回值。
}

qsort(in,100,sizeof(in[0]),compare);

復制

二.sort函數

常用于C++中，頭文件為algorithm。

用法：

sort(first,last)
在[first, last)中的元素進行排序按升序排列

復制

注意：sort默認排序后是升序。如果要想按降序排列，需自己編寫一個比較函數來實現。

sort(begin,end)，表示一個范圍，例如：

int _tmain(int argc, _TCHAR* argv[])
{
    int a[20]={2,4,1,23,5,76,0,43,24,65},i;
    for(i=0;i<20;i++)
         cout<<a[i]<<endl;
    sort(a,a+20);  //按升序排序
    for(i=0;i<20;i++)
    cout<<a[i]<<endl;
    return 0;
}

復制

輸出結果將是把數組a按升序排序，說到這里可能就有人會問怎么樣用它降序排列呢？這就是下一個討論的內容.

一種是自己編寫一個比較函數來實現，接著調用三個參數的sort：sort(begin,end,compare)就成了。對于list容器，這個方法也適用，把compare作為sort的參數就可以了，即：sort(compare).

1.自己編寫compare函數：

bool compare(int a,int b)
{
      return a<b;   //升序排列，如果改為return a>b，則為降序

}

int _tmain(int argc, _TCHAR* argv[])
{
     int a[20]={2,4,1,23,5,76,0,43,24,65},i;
     for(i=0;i<20;i++)
       cout<<a[i]<<endl;
     sort(a,a+20,compare);
     for(i=0;i<20;i++)
       cout<<a[i]<<endl;
     return 0;
}

復制

2.更進一步，讓這種操作更加能適應變化。也就是說，能給比較函數一個參數，用來指示是按升序還是按降序排,這回輪到函數對象出場了。

為了描述方便，我先定義一個枚舉類型EnumComp用來表示升序和降序。很簡單：

enum Enumcomp{ASC,DESC};

然后開始用一個類來描述這個函數對象。它會根據它的參數來決定是采用“<”還是“>”。

class compare
{
      private:
            Enumcomp comp;
      public:
            compare(Enumcomp c):comp(c) {};
      bool operator () (int num1,int num2)
         {
            switch(comp)
              {
                 case ASC:
                        return num1<num2;
                 case DESC:
                        return num1>num2;
              }
          }
};

復制

接下來使用 sort(begin,end,compare(ASC)實現升序，sort(begin,end,compare(DESC)實現降序。

主函數為：

int main()
{
     int a[20]={2,4,1,23,5,76,0,43,24,65},i;
     for(i=0;i<20;i++)
         cout<<a[i]<<endl;
     sort(a,a+20,compare(DESC));
     for(i=0;i<20;i++)
         cout<<a[i]<<endl;
     return 0;
}

復制

3.其實對于這么簡單的任務（類型支持“<”、“>”等比較運算符），完全沒必要自己寫一個類出來。標準庫里已經有現成的了，就在 functional里，include進來就行了。functional提供了一堆基于模板的比較函數對象。它們是（看名字就知道意思 了）：equal_to<Type>、not_equal_to<Type>、greater<Type>、 greater_equal<Type>、less<Type>、less_equal<Type>。對于這個問題 來說，greater和less就足夠了，直接拿過來用：

• 升序：sort(begin,end,less<data-type>());
• 降序：sort(begin,end,greater<data-type>()).

int _tmain(int argc, _TCHAR* argv[])
{
      int a[20]={2,4,1,23,5,76,0,43,24,65},i;
      for(i=0;i<20;i++)
          cout<<a[i]<<endl;
      sort(a,a+20,greater<int>());
      for(i=0;i<20;i++)
          cout<<a[i]<<endl;
      return 0;
}

復制

?4.既然有迭代器，如果是string 就可以使用反向迭代器來完成逆序排列，程序如下：

int main()
{
     string str("cvicses");
     string s(str.rbegin(),str.rend());
     cout << s <<endl;
     return 0;
}