C++

参考

<cstdlib> (stdlib.h)

函数
<cstdlib>

qsort

void qsort (void* base, size_t num, size_t size,            int (*compar)(const void*,const void*));
对数组元素进行排序
使用 compar 函数来确定顺序，对 base 指向的数组中的 num 个元素进行排序，每个元素长 size 字节。

此函数所使用的排序算法通过调用指定的 compar 函数来比较成对的元素，并将指向它们的指针作为参数。

该函数不返回任何值，但会修改 base 指向的数组内容，根据 compar 的定义重新排序其元素。

等价元素的顺序是未定义的。

参数

base
指向待排序数组第一个对象的指针，已转换为 void*。
num
base 所指向数组中的元素数量。
size_t 是一个无符号整数类型。
size
数组中每个元素的字节大小。
size_t 是一个无符号整数类型。
compar
指向一个比较两个元素的函数的指针。
此函数被 qsort 重复调用以比较两个元素。它应遵循以下原型：
1
 
int compar (const void* p1, const void* p2);
接收两个指针作为参数（均转换为const void*）。该函数通过返回以下值（以稳定且可传递的方式）来定义元素的顺序：
返回值含义
<0p1 指向的元素排在 p2 指向的元素之前
0p1 指向的元素与 p2 指向的元素等价
>0p1 指向的元素排在 p2 指向的元素之后

对于可以使用常规关系运算符进行比较的类型，一个通用的 compar 函数可能如下所示：

1
2
3
4
5
6
 
int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a <  *(MyType*)b ) return -1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
}

返回值

无

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/* qsort example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

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;
}

输出

10 20 25 40 90 100


复杂度

未指定，但快速排序通常在 num 上是线性对数级的（平均情况），大约调用 compar 函数 num*log2(num) 次。

数据竞争

该函数访问和/或修改由 base 指向的数组中的 num 个元素。

异常 (C++)

如果 comp 不抛出异常，则此函数不抛出异常（无抛出保证）。

如果 base 指向的数组没有至少 num*size 字节，或者如果 comp 的行为与上述描述不符，将导致未定义行为。

另见

bsearch
在数组中进行二分查找 (函数)