执行排序的 C 库函数

C 标准库中是否有可用的库函数来进行排序？

237686 次浏览
小开

在 stdlib.h中有几个 C 排序函数可用。你可以在 unix 机器上执行 man 3 qsort来获得它们的清单，但它们包括:

  • 堆排序
  • quicksort
  • 合并排序
小开

在 stdlib.h 中尝试 qsort。

小开

可以肯定的是: qsort()是一种排序的实现(不一定像它的名字所暗示的那样是快速排序)。

Try man 3 qsort or have a read at http://linux.die.net/man/3/qsort

小开

qsort()就是你要找的函数。您可以使用一个指针来调用它，该指针指向您的数据数组、该数组中的元素数、每个元素的大小以及一个比较函数。

它完成了它的魔法，并且您的数组就地排序:

#include <stdio.h>
#include <stdlib.h>
int comp (const void * elem1, const void * elem2)
{
int f = *((int*)elem1);
int s = *((int*)elem2);
if (f > s) return  1;
if (f < s) return -1;
return 0;
}
int main(int argc, char* argv[])
{
int x[] = {4,5,2,3,1,0,9,8,6,7};


qsort (x, sizeof(x)/sizeof(*x), sizeof(*x), comp);


for (int i = 0 ; i < 10 ; i++)
printf ("%d ", x[i]);


return 0;
}
小开

在 <stdlib.h>中使用 qsort()。

@ paxDiablo qsort()功能符合 ISO/IEC9899:1990(“ ISOC90”)。

小开

C++标准程式库 <stdlib.h>包含 qsort功能。

这不是世界上最好的快速排序实现，但它足够快，而且非常快 易于使用... qsort 的正式语法是:

qsort(<arrayname>,<size>,sizeof(<elementsize>),compare_function);

The only thing that you need to implement is the compare_function, which takes in two 类型为“ const void”的参数，它可以转换为适当的数据结构，然后 返回以下三个值之一:

  • 如果 a 在 b 之前，则为负
  • 如果 a 等于 b
  • positive, if a should be after b

1. 比较整数列表 :

简单地将 a 和 b 转换为整数 if x < y,x-y is negative, x == y, x-y = 0, x > y, x-y is positive x-y是这样做的一种快捷方式:) 将 *x - *y反转到 *y - *x，以减少/反转顺序排序

int compare_function(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}

2. 比较字符串列表 :

为了比较字符串，需要在 <string.h> lib 中使用 strcmp函数。 在默认情况下，strcmp将返回-ve，0，ve... 以相反的顺序进行排序，只需反转 strcmp 返回的符号即可

#include <string.h>
int compare_function(const void *a,const void *b) {
return (strcmp((char *)a,(char *)b));
}

3. 比较浮点数 :

int compare_function(const void *a,const void *b) {
double *x = (double *) a;
double *y = (double *) b;
// return *x - *y; // this is WRONG...
if (*x < *y) return -1;
else if (*x > *y) return 1; return 0;
}

4. 根据键 比较记录:

Sometimes you need to sort a more complex stuffs, such as record. Here is the simplest 使用 qsort库的方法。

typedef struct {
int key;
double value;
} the_record;


int compare_function(const void *a,const void *b) {
the_record *x = (the_record *) a;
the_record *y = (the_record *) b;
return x->key - y->key;
}
小开

虽然不在标准库中，但是 https://github.com/swenson/sort只有两个头文件，你可以通过这两个头文件访问一系列难以置信的快速排序路由，比如:

#define SORT_NAME int64
#define SORT_TYPE int64_t
#define SORT_CMP(x, y) ((x) - (y))
#include "sort.h"
/* You now have access to int64_quick_sort, int64_tim_sort, etc., e.g., */
int64_quick_sort(arr, 128); /* Assumes you have some int *arr or int arr[128]; */

This should be at least twice as fast as the standard library qsort, since it doesn't use function pointers, and has many other sorting algorithm options to choose from.

它在 C89中，所以基本上可以在每个 C 编译器中工作。

小开

我想你要找的是 qsort。
qsort函数是 C/C++中 stdlib.h中的快速排序算法的实现。

下面是调用 qsort函数的语法:

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

论据清单:

Base : 指向数组的第一个元素或基地址的指针
Nmemb : 数组中的元素数
size: size in bytes of each element
Compar : 比较两个元素的函数

下面是一个使用 qsort对数组进行排序的代码示例:

#include <stdio.h>
#include <stdlib.h>


int arr[] = { 33, 12, 6, 2, 76 };


// compare function, compares two elements
int compare (const void * num1, const void * num2) {
if(*(int*)num1 > *(int*)num2)
return 1;
else
return -1;
}


int main () {
int i;


printf("Before sorting the array: \n");
for( i = 0 ; i < 5; i++ ) {
printf("%d ", arr[i]);
}
// calling qsort
qsort(arr, 5, sizeof(int), compare);


printf("\nAfter sorting the array: \n");
for( i = 0 ; i < 5; i++ ) {
printf("%d ", arr[i]);
}
  

return 0;
}

您可以在 Linux/Mac 终端中键入 man 3 qsort以获得关于 qsort的详细信息。
链接到 qsort 手册页

小开

Stdlib 中的 GNU qsort 源代码显示它是快速排序。


提交答案