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
在陣列中進行二分查詢 (函式)