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