qsort-c和c++标准函数

C&C++标准库

qsort

函数 <cstdlib>

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

数组元素排序

使用compare函数对指向数组的num元素按base(每个元素的长度为字节)排序，以确定顺序。

该函数使用的排序算法通过调用指定的compare函数，将元素对的指针作为参数进行比较。

该函数不返回任何值，但修改由base指向的数组的内容，并按照compar定义对其元素重新排序。

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

☲ 参数

base
指向要排序的数组的第一个对象的指针，类型转换为void*。

num
数组中元素的个数.
Size_t是一个无符号整型。

size
数组中每个元素的字节大小。
Size_t是一个无符号整型。

compar
指向比较两个元素的函数的指针。
qsort会反复调用这个函数来比较两个元素。它将遵循以下原型:

int compar (const void* p1, const void* p2);

接受两个指针作为实参(都转换为const void*)。该函数通过返回(以稳定和可传递的方式)来定义元素的顺序:

返回值	意思是
<0	p1指向的元素在p2指向的元素之前
0	p1所指向的元素与p2所指向的元素等价
>0	p1指向的元素在p2指向的元素之后

对于可以使用常规关系操作符进行比较的类型，一般的比较函数可能如下所示:

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

☉ 返回值

none

☣ 示例

/* 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中是线性的，平均而言，调用比较大约num*log2(num)次。

↭ 数据竞争

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

❆ 异常(c++)

如果comp不抛出异常，则此函数不抛出异常(no-throw保证)。

如果base不指向一个至少包含num*size字节的数组，或者如果comp的行为不像上面描述的那样，它将导致未定义的行为。

🍄 另请参阅

bsearch

二分查找数组(function )