C++ qsort函數詳解

一、qsort函數介紹

qsort函數是C++標準庫中的一個快速排序函數，用於對任意類型的數組進行排序。它的原型如下：

void qsort ( void * base, size_t num, size_t size,
             int ( * comparator ) ( const void *, const void * ) );

該函數接收四個參數：

• base：指向需要排序的數組的首元素的指針。
• num：數組中元素的個數。
• size：數組中每個元素的字節數。
• comparator：指向比較函數的指針，用於定義排序規則。

二、使用方法

為了使用qsort函數，需要提供一個用來比較數組元素的函數。

因為qsort函數是通用的，可以對任意類型的數組進行排序，所以比較函數需要具有通用性。

比較函數的原型如下：

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

該函數接收兩個指向常量的void指針，即指向要比較的兩個元素。

如果第一個元素小於第二個元素，則函數返回一個負數；如果兩個元素相等，則返回0；如果第一個元素大於第二個元素，則返回一個正數。

下面是一個示例的比較函數，用於對整數數組進行升序排序：

int compare (const void * a, const void * b) {
  return ( *(int*)a - *(int*)b );
}

最後，我們可以用類似下面的方式調用qsort函數來排序一個整數數組：

int numbers[] = { 5, 2, 9, 4, 8, 3, 1, 6, 7 };
int size = sizeof(numbers)/sizeof(int);
qsort (numbers, size, sizeof(int), compare);

三、性能考慮

qsort函數的時間複雜度為O(nlogn)。在大多數情況下，它是一種非常高效的排序算法。然而，在某些情況下，它的性能可能會受到排序指針本身順序的影響。

在最壞情況下，qsort的時間複雜度可能會退化到O(n^2)。為了避免這種情況，在實際使用中，可以通過使用一些優化技巧來提高qsort的性能。

例如，可以在排序前對數組進行隨機打亂，或者在數組長度比較小的情況下，使用插入排序或冒泡排序等簡單但高效的排序算法。

四、實例代碼

下面是一個完整的示例代碼，展示如何使用qsort函數對一個字符串數組進行排序：

#include 
#include 
#include 
#include 

using namespace std;

int compare (const void * a, const void * b) {
  return strcmp(*(const char **)a, *(const char **)b);
}

int main () {
  const char * fruits[] = {"apple", "banana", "orange", "pear", "kiwi"};
  int size = sizeof(fruits)/sizeof(char*);
  qsort(fruits, size, sizeof(char*), compare);
  for (int i=0; i<size; i++) {
    cout << fruits[i] << endl;
  }
  return 0;
}